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.

Input

Output

Example

fixprefixsuffix

fix

abcdabc

Just a legend

计算出next数组，再用贪心的方法匹配看是否前后缀相同且中间也出现过。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 char s[1000005];
 6 int Next[1000005],c[1000005];
 7 
 8 void getnext(char* s,int m)
 9 {
10     Next[0]=0;
11     Next[1]=0;
12     for(int i=1;i<m;i++)
13     {
14         int j=Next[i];
15         while(j&&s[i]!=s[j])
16             j=Next[j];
17         if(s[i]==s[j])
18             Next[i+1]=j+1;
19             else
20                 Next[i+1]=0;
21     }
22 }
23 
24 int main()
25 {
26     scanf("%s",s);
27     int n=strlen(s);
28     getnext(s,n);
29     for(int i=0;i<n;i++)
30         c[Next[i]]=1;
31     c[0]=0;
32     for(int i=n;i;i=Next[i])
33         if(c[Next[i]]==1)
34         {
35             for(int j=0;j<Next[i];j++)
36                 printf("%c",s[j]);
37             return 0;
38         }
39     printf("Just a legend");
40     
41     return 0;
42 }

CodeForces - 126B Password