Problem: 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

You are given the string s whose length can vary from 1 to 106 (inclusive), consisting of small Latin letters.

Output

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

Examples

Input

fixprefixsuffix


Output

fix

Input

abcdabc


Output

Just a legend

Solution (in PYTHON3):

Solution:
import bisect
def ZAlgo(s):
    z=[0]*len(s)
    left=right=0
    for k in range (1,len(s)):
        if k > right:
            left=right=k
            while(right < len(s) and s[right] == s[right-left]):
                right+=1
            z[k]=right-left
            right-=1
        else:
            k1=k-left
            if z[k1] < right - k + 1:
                z[k]=z[k1]
            else:
                left=k
                while(right < len(s) and s[right] == s[right-left]):
                    right+=1
                z[k]=right-left
                right-=1
    return z
pat=input();M=len(pat)
z=ZAlgo(pat);c=1;suf=[];count=0;m=0
for i in range(len(z)):
    if z[i]>0:
        p=i
        break
##print (z)
##print (len(pat)-p)
suffix={}
for i in range(M-1,-1,-1):
    if z[i]==c and z[i]<len(pat)-p:
        suf.append(z[i])
        suffix[z[i]]=i
    c+=1
suf=sorted(suf)
#print (suffix)
if len(suf)>1:
    #print(pat[:suf[-2]])
    for i in range(len(z)):
        if z[i] not in suffix or suffix[z[i]]!=i:
            m=max(m,bisect.bisect_right(suf,z[i]))
    print (pat[:suf[m-1]])
elif len(suf)==1:
    for i in z:
        if i>=suf[0]:
            count+=1
    if count>=2:
        print (pat[:suf[0]])
    else:
        print ('Just a legend')
else:
    print ('Just a legend')