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 sys

I = lambda: int(input())
readline = lambda : sys.stdin.readline().strip()
RM = readlist = lambda x=int: map(x,readline().split())


def prefix_function(s):
    n  = len(s)
    pi = [0]*(n)
    for i in range(1,n):
        j = pi[i-1]
        while j>0 and s[i]!=s[j]:
            j = pi[j-1]#reduce s to last largest prefix of i
        if s[i] == s[j]: j+=1
        pi[i] = j
    return pi

s = readline()
pi = prefix_function(s)
pis = set(pi[:-1])
j = pi[-1]
while j>0 and (not j in pis):
    j = pi[j-1]
print(s[:j] if j>0 else "Just a legend")


quit()
#154C Double Profiles (failure)
s = readline()
n = len(s)
ppow,base,p,m = [0]*int(n+5),1,31,int(1e9+7)
for i in range(n+5):
    ppow[i],base = base,(base*p)%m

hashp = [0]*n

hashp[0] = ord(s[0]) - 96
for ind in range(1,n):
    hashp[ind] = (hashp[ind-1] + (ord(s[ind])-96)*ppow[ind])%m

stop = False
for l in range(n-1,0,-1):
    prefix_hash =                (   hashp[l-1]*ppow[n+1] )%m
    suffix_hash = ( (hashp[n-1] - hashp[n-l-1])*ppow[l+1] )%m
    #print(l,suffix_hash,prefix_hash)
    if suffix_hash!=prefix_hash:    continue
    for t in range(1,n-l):
        temp_hash = ( (hashp[t+l-1] - hashp[t-1])*ppow[n-t+1] )%m
        if temp_hash == suffix_hash:
            print(s[t:t+l]);stop = True;break
    if stop: break
else:
    print("Just a legend")