Good Luck!

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

我们都知道,前缀就是一个单词的前几个字母(长度小于单词长度);后缀就是一个单词的后几个字母(长度小于单词长度)。例如:Hello,{H,He,Hel,Hell}都是Hello的前缀,{ello,llo,lo,o}都是Hello的后缀。现在,给你一个字符串String,你的任务是找出一个字串s,s既是String的前缀,又是String的后缀,并且s也出现在String的中间部分(既不是前缀,也不是后缀),s的长度越长越好。

Input

输入一个N,接下来N行,每行一个字符串String,String长度len( 1 <= len <= 1000000)。

Output

输出只有一行,如果有符合条件的s,输出长度最长的s,如果没有,输出“Bad Luck!”(不含引号)。

Sample Input

3
abcabcabcabcabc
papapapap
aaabaaaabab

Sample Output

abcabcabc
papap
Bad Luck!

Hint

 

Source

GLSilence