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.util.*;

public class Main{

	// code from geekForGeeks - KMP Algorithm for Pattern Searching
	public static Integer[] computeLPSArray(String pat, int M, Integer lps[]) { 
        // length of the previous longest prefix suffix 
        int len = 0; 
        int i = 1; 
        lps[0] = 0; // lps[0] is always 0 
  
        // the loop calculates lps[i] for i = 1 to M-1 
        while (i < M) { 
            if (pat.charAt(i) == pat.charAt(len)) { 
                len++; 
                lps[i] = len; 
                i++; 
            } 
            else // (pat[i] != pat[len]) 
            { 
                // This is tricky. Consider the example. 
                // AAACAAAA and i = 7. The idea is similar 
                // to search step. 
                if (len != 0) { 
                    len = lps[len - 1]; 
  
                    // Also, note that we do not increment 
                    // i here 
                } 
                else // if (len == 0) 
                { 
                    lps[i] = len; 
                    i++; 
                } 
            } 
        } 
		return lps;
    } 
	
	public static void main(String args[]){
		//String st = "fixprefixsuffix";
		Scanner stdin = new Scanner(System.in);
		String st = stdin.nextLine();
		int size = st.length();
		Integer lps[] = new Integer[size]; 
		Integer x[] = computeLPSArray(st,size,lps);
		
		//System.out.println(Arrays.toString(x));
		
		
			
		int max = Collections.max(Arrays.asList(x));
		//System.out.println("Max: "+max);
		if(x[size-1] == 2*(size/3) && max != 0)
			System.out.println(st.substring(size-(max/2)));
		else if(x[size-1] <= max && x[size-1]!=0 && max != 0 && size>2){
			boolean found = false;
			max = x[size-1];
			for(int i= max-1; i<(size-1); i++){
				//System.out.println("i: "+i);
				if(x[i] == max){
					found = true;
					break;
				}
			}
			if(found)
				System.out.println(st.substring(size-max));
			else{
				if(x[max-1] != 0)
					System.out.println(st.substring(size-x[max-1]));
				else
					System.out.println("Just a legend");}
		}
		else
			System.out.println("Just a legend");
		
	}
}