TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

58.8% (10/17)

Submission's AC Ratio

12.6% (29/231)

Description

今天又是小杰所期待的奇數月的25號,因為又可以對統一發票了!
小杰對小錢沒什麼感覺,所以他只在意其中的最大獎,也就是一千萬元的特別獎。

在小杰所住的國度中,他們統一發票的號碼是由小寫字母組成的非空字串,想當然爾,他們國的特別獎號碼也是由小寫字母組成的非空字串。而且他們的制度非常神奇,他們每張統一發票號碼的長度不一定相同,而且每一期的特別獎號碼長度也不一定相同。
要怎麼判斷一張發票有沒有對中特別獎呢?
如果該張發票的號碼中恰好只有一段連續的部分跟特別獎號碼完全相同就好了。
更精確來說,假設特別獎號碼$x$的長度為$L_1$,對於一個長度為$L_2$的統一發票號碼$y$中恰好有一個位置$p(1 \leq p \leq L_2-L_1+1)$,符合$\forall 1 \leq i \leq L_1$,$x_i = y_{p+i-1}$,就代表這張發票就有對中特別獎,可以準備開開心心去領錢!
小杰在對完發票之後,開開心心地拿著一堆發票去找你,然後跟你說:「這些發票全都有對中特別獎喔!」
請根據小杰給你的發票來決定特別獎可能長甚麼樣子,或是小杰視力不好對錯了,這些發票不可能每張都對中特別獎。

Input Format

第一行有一個整數$N$,代表小杰帶來了幾張統一發票。
接下來$N$行中的第$i$行有一個由小寫字母組成的字串$S_i$,代表第$i$張發票上的號碼。

Output Format

請輸出一個字串於一行,代表任一種可能的特別獎號碼。
如果不存在符合的特別獎號碼,請輸出一行 7122

Sample Input

Sample Input 1
1
xiaozihong

Sample Input 2
5
ramen
lamian
raaamen
yesiam
diamond

Sample Input 3
4
jizz
jizzz
jizzzzz
jizjiz

Sample Output

Sample Output 1
zihong

Sample Output 2
am

Sample Output 3
7122

Hints

希望不要被假解QQ

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~2 $N = 1$ 4
2 3~7 $1\leq N \leq \sum |S_i| \leq 20$ 6
3 3~17 $1\leq N \leq\sum |S_i| \leq 300$ 15
4 3~26 $1\leq N \leq\sum |S_i| \leq 3500$ 25
5 0~39 $1\leq N \leq\sum |S_i| \leq 2 \times 10^ 5$ 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 5
1 1000 524288 65536 1 5
2 1000 524288 65536 1 5
3 1000 524288 65536 2 3 4 5
4 1000 524288 65536 2 3 4 5
5 1000 524288 65536 2 3 4 5
6 1000 524288 65536 2 3 4 5
7 1000 524288 65536 2 3 4 5
8 1000 524288 65536 3 4 5
9 1000 524288 65536 3 4 5
10 1000 524288 65536 3 4 5
11 1000 524288 65536 3 4 5
12 1000 524288 65536 3 4 5
13 1000 524288 65536 3 4 5
14 1000 524288 65536 3 4 5
15 1000 524288 65536 3 4 5
16 1000 524288 65536 3 4 5
17 1000 524288 65536 3 4 5
18 1000 524288 65536 4 5
19 1000 524288 65536 4 5
20 1000 524288 65536 4 5
21 1000 524288 65536 4 5
22 1000 524288 65536 4 5
23 1000 524288 65536 4 5
24 1000 524288 65536 4 5
25 1000 524288 65536 4 5
26 1000 524288 65536 4 5
27 1000 524288 65536 5
28 1000 524288 65536 5
29 1000 524288 65536 5
30 1000 524288 65536 5
31 1000 524288 65536 5
32 1000 524288 65536 5
33 1000 524288 65536 5
34 1000 524288 65536 5
35 1000 524288 65536 5
36 1000 524288 65536 5
37 1000 524288 65536 5
38 1000 524288 65536 5
39 1000 524288 65536 5