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

import static java.lang.Math.* ;
import static java.util.Arrays.* ;

public class E {
	
	public static void main(String[] args) throws IOException {
		
		new E().solveProblem();
		
		out.close();
	}

	static Input in = new Input() ;
	static PrintStream out = new PrintStream(new BufferedOutputStream(System.out));	
	static Output out2 = new Output(out) ;
	
	long MOD = 1000000007L;
	long M = 29L;
	
	public void solveProblem() throws IOException {		
	
	    String input = in.next();
	    
        String tekst = input.substring(1);
        String pattern = input;

        T = tekst.toCharArray();
        n = T.length;
        P = pattern.toCharArray();
        m = P.length;

        b = new int[m + 1];

        preprocess();
        kmp();

        long[] p = new long[n+1];
        p[0] = 1;
        for( int i = 1; i <=n ; i++)
            p[i] = (p[i-1]*M)%MOD;
        
        long hash1 = 0;
        long hash2= 0;
        

        
        
        for( int i = 0 ; i < max ; i++){
            
            hash1 = (hash1*M+P[i]-'a')%MOD;
            hash2 = (hash2+p[i]*(P[m-1-i]-'a'))%MOD;
            
  

            if( hash1 == hash2)
                sol = i + 1;
        }

        
        if( sol == 0)
            out.println("Just a legend");
        else
            out.println(input.substring(0,sol));
		
	}
	
	int max = 0;
	int max2 = 0;
	
	int sol = 0;
	
    

    char[] T;
    char[] P;
    int[] b;

    int n, m;

    void preprocess() {

        int i = 0;
        int j = -1;
        b[0] = -1;

        while (i < m) {
            while (j >= 0 && P[i] != P[j])
                j = b[j];
            i++;
            j++;
            b[i] = j;
        }
    }

    void kmp() {

        int i = 0;
        int j = 0;

        while (i < n) {

            while (j >= 0 && T[i] != P[j])
                j = b[j];
            i++;
            j++;

            
            if( i < n){
                max = max(max,j);

            }
            if (j == m) {
                // gev ;
               // System.out.println(i - j);
                j = b[j];
            }
        }
        
        max2 = j;

    }
	
	static void p( Object ...p){
		System.out.println(Arrays.deepToString(p));
	}
	
	static class Input {	
		
		BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer tokens ;
		
		public int nextInt(){
			return Integer.parseInt(next()) ;
		}

		public int[] nextInt(int n ){
			int[] res = new int[n] ;
			for( int i = 0 ; i < n ; i++ )
				res[i] = nextInt() ;
			return res ;
		}

		public long nextLong(){
			return Long.parseLong(next()) ;
		}

		public long[] nextLong(int n ){
			long[] res = new long[n] ;
			for( int i = 0 ; i < n ; i++ )
				res[i] = nextLong() ;
			return res ;
		}
		
		public double nextDouble(){
			return Double.parseDouble(next()) ;
		}
		
		public String next(){
			
			try{
				while( tokens == null || !tokens.hasMoreTokens() )
					tokens = new StringTokenizer(buf.readLine()) ;
			}catch( Exception e ){
				e.printStackTrace() ;
			}
			
			return tokens.nextToken() ;
		}

	}

	static class Output {
		
		PrintStream out ;
		
		public Output(PrintStream out) {
			this.out = out;
		}

		void wr( int[] rij ){
			for( int i = 0 ; i < rij.length - 1 ; i++ ) 
				out.print(rij[i] + " ") ;
			out.println(rij[rij.length-1]);		
		}

		void wr( long[] rij ){
			for( int i = 0 ; i < rij.length - 1 ; i++ ) 
				out.print(rij[i] + " ") ;
			out.println(rij[rij.length-1]);		
		}
		
		void wr( char[] rij){
			out.println(new String(rij)) ;
		}
		
	}
}