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 JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main{
  public static void kmp(String a)
{
	
	char c[]=a.toCharArray();
	int arr[]=new int[c.length];
	int len=0;
	int n=c.length;
	int i=1;
	arr[0]=0;
	while(i<n)
	{
		if(c[i]==c[len])
		{
			len++;                   
			arr[i]=len;
			i++;
						
			
		}
		else{
			
			if(len!=0)
			{
				len=arr[len-1];
				
			}
			else{
				
				arr[i]=len;
				i++;
			}
		}
		
		
	}
	
//	for(i=0;i<arr.length;i++)
//	System.out.println(arr[i]);
	
	if(arr[c.length-1]>0)
	{  
		int k=c.length-1;
        int f=arr.length-1;
        int j=99999;
        int max;
        int h;
		do{
	    
		 max=0;
		
		for(i=f-1;i>=0;i--)
		{
			max=Math.max(arr[i],max);
			f=i;
		//System.out.println(max);
		//	System.out.println(arr[max]);
			if(arr[i]==arr[k])
			{
				System.out.println(a.substring(0,arr[i]));
				return;
			}
			
		}
		j=arr[max];
		
		}while(j>arr[k]&& f>1);
		 if(j==0)
		{
			System.out.println("Just a legend");
		}
		else{
		System.out.println(a.substring(0,j));
		}
		return;
		
	}
	
	
		
	System.out.println("Just a legend");
	return;
	
	
}
		
		public static void main(String[] args)throws Exception {
			BufferedReader  br=new BufferedReader(new InputStreamReader(System.in));
			String a=br.readLine();
			
			kmp(a);
			
			
			
		}
	}