← 返回题目列表

Codeforces · 126/B

B. 密码

中文机器翻译题面 查看原题

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