Corporate Identity

Time limit1sMemory limit128 MB

Summary

Given up to 4000 short lowercase strings, find the longest string that occurs as a contiguous substring of every one, breaking ties by lexicographic order.

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

Problem

Besides its other services, ACM helps companies to clearly state their "corporate identity", which includes the company logo but also other signs such as trademarks. One such company is Internet Building Masters (IBM), which has recently asked ACM for help with its new identity. IBM does not want to change its existing logos and trademarks completely, because its customers are already used to the old ones. Therefore, ACM will only adjust the existing trademarks instead of creating new ones.

After several proposals, it was decided to take all of the existing trademarks and find the longest sequence of letters that appears, as a contiguous substring, in every one of them. This sequence will be graphically emphasized to form a new logo, so that the old trademarks can still be used while showing the new identity.

Your task is to find such a sequence.

Input

The input contains several tasks. Each task begins with a line containing a positive integer $N$ , the number of trademarks ( $2 \le N \le 4000$ ). This is followed by $N$ lines, each containing one trademark. Every trademark consists of lowercase letters only, and its length is at least $1$ and at most $200$ characters.

Immediately after the last trademark of a task, the next task begins. The last task is followed by a line containing a single $0$ .

Output

For each task, output a single line containing the longest string that appears as a contiguous substring in all of the trademarks. If several strings share this maximum length, print the lexicographically smallest one. If no such non-empty string exists, output the words "IDENTITY LOST" instead.

Examples4

Example 1

Input

3
aabbaabb
abbababb
bbbbbabb
2
xyz
abc
0

Expected output

abb
IDENTITY LOST

Example 2
Input
```
2
abcabc
abcabc
0
```
Expected output
```
abcabc
```
Example 3
Input
```
2
aaaa
bbbb
0
```
Expected output
```
IDENTITY LOST
```
Example 4
Input
```
2
abba
baab
0
```
Expected output
```
ab
```