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:
#code
import sys
import math as mt
#input=sys.stdin.buffer.readline
#t=int(input())
#tot=0
t=1

def getZarr(string, z): 
	n = len(string) 

	# [L,R] make a window which matches 
	# with prefix of s 
	l, r, k = 0, 0, 0
	for i in range(1, n): 

		# if i>R nothing matches so we will calculate. 
		# Z[i] using naive way. 
		if i > r: 
			l, r = i, i 

			# R-L = 0 in starting, so it will start 
			# checking from 0'th index. For example, 
			# for "ababab" and i = 1, the value of R 
			# remains 0 and Z[i] becomes 0. For string 
			# "aaaaaa" and i = 1, Z[i] and R become 5 
			while r < n and string[r - l] == string[r]: 
				r += 1
			z[i] = r - l 
			r -= 1
		else: 

			# k = i-L so k corresponds to number which 
			# matches in [L,R] interval. 
			k = i - l 

			# if Z[k] is less than remaining interval 
			# then Z[i] will be equal to Z[k]. 
			# For example, str = "ababab", i = 3, R = 5 
			# and L = 2 
			if z[k] < r - i + 1: 
				z[i] = z[k] 

			# For example str = "aaaaaa" and i = 2, 
			# R is 5, L is 0 
			else: 

				# else start from R and check manually 
				l = i 
				while r < n and string[r - l] == string[r]: 
					r += 1
				z[i] = r - l 
				r -= 1

for __ in range(t):
    #n=int(input())      
    #l=list(map(int,input().split()))  
    #n,m=map(int,input().split())            
    #l=list(map(int,input().split()))
    s=input()
    z=[0]*(len(s)+1)
    d={}

    n=len(s)    
    getZarr(s, z)
    #print(z)
    d=[]
    maxm=-1
    for i in range(len(s)):
        if i+z[i]!=n:
            maxm=max(maxm,z[i])
        else:
            d.append(z[i])
    maxi=-1
    d.sort()
    for i in range(len(s)):
        if i+z[i]==n:
            if maxm>=z[i]:
                maxi=max(maxi,z[i])
            if d[-1]!=z[i]:
                maxi=max(maxi,z[i])
    if maxi>0:
        print(s[:maxi])
    else:
        print("Just a legend")