TopCoder

Thumb fhvirus icon.001
FHVirus
"FHVirus 是一種由主要由IO組合而成的病毒。"

User's AC Ratio

89.5% (51/57)

Submission's AC Ratio

59.0% (85/144)

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}$,就代表這張發票有對中「增開六獎」,可以準備開開心心去領錢!

小紅在對完發票之後,開開心心地拿著一堆發票去找你,然後跟你說:
「這些發票全都有對中200元喔!而且都剛好是增開六獎呢!沒想到我一開始都忘了有增開六獎呀。」
請根據小紅給你的發票來決定「增開六獎」可能長甚麼樣子,或是小紅視力不好對錯了,這些發票不可能每張都對中「增開六獎」。

Input Format

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

Output Format

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

Sample Input

Sample Input 1
1
plghlgrtgd

Sample Input 2
5
wlch
gfeo
pgbe
jwuv
dnbu

Sample Input 3
2
pkqmx
tiyx

Sample Output

Sample Output 1
lg

Sample Output 2
7122

Sample Output 3
x

Hints

$\sum |S_i| \leq 2 \times 10^ 5$,其中 $|S_i|$ 代表 $S_i$ 這個字串的長度。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~14 $N \leq 10^ 5, \sum |S_i| \leq 2 \times 10^ 5$ 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 1
6 1000 262144 65536 1
7 1000 262144 65536 1
8 1000 262144 65536 1
9 1000 262144 65536 1
10 1000 262144 65536 1
11 1000 262144 65536 1
12 1000 262144 65536 1
13 1000 262144 65536 1
14 1000 262144 65536 1