Lock
By Microsoft
Serbia
By Microsoft Serbia
In a dark basement, there is a wooden case with printed solutions to all tasks in this contest. However, the basement has thick walls and a door, and a lock on the door. On the lock, there are n horizontal iron bars, and on each of the bars there is a word with letters of equal width. Each bar can be moved independently to the left or right for one or more widths of a letter. There is at least one letter that is common to all words. Therefore, bars can be lined up so that there is a vertical line of n identical letters above each other (each letter on one bar). To unlock the door, bars should be positioned in such a way that there is a maximal number of such consecutive vertical lines.
You are naturally interested in writing a program that solves this problem.
First line contains a number n, the number of bars, with n <= 1000. In each of next n lines, there is a word corresponding to one of the bars. Each word contains only capital letters, and is at least 1 and at most 100 characters long.
A string of maximal length, that appears in every word as a sequence of consecutive letters. If there is more than one solution, you should print the leftmost one.
| Input Sample | Output Sample |
|
3 |
TBAL |