Password

题意翻译

Asterix，Obelix和他们的临时伙伴Suffix、Prefix已经最终找到了和谐寺。然而和谐寺大门紧闭，就连Obelix的运气也没好到能打开它。 不久他们发现了一个字符串S（|S|<=1000000），刻在和谐寺大门下面的岩石上。Asterix猜想那一定是打开寺庙大门的密码，于是就大声将字符串朗读了出来，然而并没有什么事发生。于是Asterix又猜想密码一定是字符串S的子串T。 Prefix认为T是S的前缀，Suffix认为T是S的后缀，Obelix却认为T应该是S中的某一部分，也就是说，T既不是S的前缀，也不是S的后缀。 Asterix选择子串T来满足所有伙伴们的想法。同时，在所有可以被接受的子串变形中，Asterix选择了最长的一个（因为Asterix喜欢长的字符串）当Asterix大声读出子串T时，寺庙的大门开了。 （也就是说，你需要找到既是S的前缀又是S的后缀同时又在S中间出现过的最长子串） 现在给你字符串S，你需要找到满足上述要求的子串T。 输入格式： 一个长度在[1,1000000]间的只包含小写字母的字符串S。 输出格式： 输出子串T，如果T不存在，输出 "Just a legend"，不包含引号。 感谢@Chemist 提供的翻译

题目描述

Asterix, Obelix and their temporary buddies Suffix and Prefix has finally found the Harmony temple. However, its doors were firmly locked and even Obelix had no luck opening them. A little later they found a string $ s $ , carved on a rock below the temple's gates. Asterix supposed that that's the password that opens the temple and read the string aloud. However, nothing happened. Then Asterix supposed that a password is some substring $ t $ of the string $ s $ . Prefix supposed that the substring $ t $ is the beginning of the string $ s $ ; Suffix supposed that the substring $ t $ should be the end of the string $ s $ ; and Obelix supposed that $ t $ should be located somewhere inside the string $ s $ , that is, $ t $ is neither its beginning, nor its end. Asterix chose the substring $ t $ so as to please all his companions. Besides, from all acceptable variants Asterix chose the longest one (as Asterix loves long strings). When Asterix read the substring $ t $ aloud, the temple doors opened. You know the string $ s $ . Find the substring $ t $ or determine that such substring does not exist and all that's been written above is just a nice legend.

输入输出格式

输入格式

You are given the string $ s $ whose length can vary from $ 1 $ to $ 10^{6} $ (inclusive), consisting of small Latin letters.

输出格式

Print the string $ t $ . If a suitable $ t $ string does not exist, then print "Just a legend" without the quotes.

输入输出样例

输入样例 #1

fixprefixsuffix

输出样例 #1

fix

输入样例 #2

abcdabc

输出样例 #2

Just a legend