During his travels in Middle-earth, Bilbo had to study many
languages. The most difficult to learn was the ancient Elvish
language Quenya. Bilbo had even acquired a parchment to which he
carefully wrote down Quenya words. By the way, Bilbo could have made mistakes when writing down the words, but he
knew exactly that there were no more than two mistakes in each word.
There could be the following mistakes: a letter was missing, an extra
letter was inserted, a letter was replaced by another letter.
When his travels were over, Bilbo decided to compile a Quenya-Westron dictionary for hobbits. He looked through his records and discovered that the same word could be written down in its correct form as well as in one or several incorrect forms, so it had possibly been put down several times.
Help Bilbo to find all possible repetitions of words in his
parchment. We know that for each word from Bilbo's parchment
its correct form is also there.
Input
The first line contains the number of words K,
1 ≤ K ≤ 5000.
In the next K lines there are the words from Bilbo's
parchment. Each word is a nonempty line containing no more than 15 symbols, which are lowercase English letters. All the words in the list are different.
Output
You must find all the words (together with their incorrect forms) that can be present in the list more than once.
In the first line output their number. Then output these words in the lexicographical order, one in a line.
Sample
input | output |
---|
7
lomba
pella
palpa
papa
moina
morna
sin | 5
moina
morna
palpa
papa
pella |
Problem Author: Sergey Pupyrev
Problem Source: VIII USU Open Personal Contest (March 3, 2007)