Life Forms

Time limit2sMemory limit128 MB

Summary

Given up to 100 DNA strings, find every longest contiguous substring that appears in strictly more than half of them, printed in alphabetical order.

Level: Medium7 of 10
Topics: String, Binary search, Hash map, Sorting
Solved: No attempts yet

Problem

You may have wondered why most extraterrestrial life forms resemble humans, differing only in superficial traits such as height, colour, wrinkles, ears and eyebrows. A few bear no human resemblance at all; these usually take geometric or amorphous shapes such as cubes, oil slicks or clouds of dust.

The reason is that the vast majority of life forms in this quadrant inherited a large fragment of common DNA.

Given the DNA sequences of several life forms, each represented as a string of letters, find the longest (contiguous) substring that is shared by more than half of them.

Input

The input consists of several test cases. Each test case begins with an integer $n$ ( $1 \le n \le 100$ ), the number of life forms. The next $n$ lines each contain a string of lowercase letters representing one life form's DNA sequence. Each DNA sequence has length between $1$ and $1000$ , inclusive. A line containing a single $0$ follows the last test case.

Output

For each test case, output the longest string (or strings) shared by more than half of the life forms. If several strings tie for the longest, output all of them in alphabetical order. If there is no answer of length at least $1$ , output ?. Leave one blank line between consecutive test cases.

Examples1

Example 1

Input

3
abcdefg
bcdefgh
cdefghi
3
xxx
yyy
zzz
0

Expected output

bcdefg
cdefgh

?