2155 . 對發票 again
TopCoder
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 1
1
xiaozihong
xiaozihong
Sample Output 1
zihong
Sample Input 2
5
ramen
lamian
raaamen
yesiam
diamond
ramen
lamian
raaamen
yesiam
diamond
Sample Output 2
am
Sample Input 3
4
jizz
jizzz
jizzzzz
jizjiz
jizz
jizzz
jizzzzz
jizjiz
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 |