Asterix、Obelix 和他们的临时好友 Suffix 和 Prefix 终于找到了和谐神殿。然而,它的门被牢牢锁住,就连奥贝利克斯也没有运气打开它。
不久之后,他们发现了一根绳子,刻在寺庙大门下方的岩石上。阿斯特克斯猜想这就是打开神殿的密码,并大声读出了字符串。然而,什么也没发生。然后 Asterix 假设密码是字符串 s 的某个子字符串 t。
前缀假设子串t是字符串s的开头; Suffix 假设子串 t 应该是字符串 s 的结尾; Obelix 认为 t 应该位于字符串 s 内部的某个位置,即 t 既不是它的开头,也不是它的结尾。
Asterix 选择子串 t 是为了取悦他所有的同伴。此外,从所有可接受的变体中,Asterix 选择了最长的一个(因为 Asterix 喜欢长弦)。当阿斯特里克斯大声读出子串t时,神庙的门打开了。
你知道字符串 s。找到子串t或者确定这样的子串不存在,上面写的只是一个很好的图例。
输入
给出的字符串 s 的长度可以在 1 到 106(含)之间变化,由小拉丁字母组成。
输出
打印字符串 t。如果不存在合适的 t 字符串,则打印“Just a legend”,不带引号。
示例
输入 #1
fixprefixsuffix
输出 #1
fix
输入 #2
abcdabc
输出 #2
Just a legend