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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.Scanner;
import java.util.TreeMap;

public class Solution{
	
	///////////////////////////////////////////////////////////////////////////
	static class FastScanner{
		BufferedReader s;
		StringTokenizer st;
		
		public FastScanner(){
			st = new StringTokenizer("");
			s = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastScanner(File f) throws FileNotFoundException{
			st = new StringTokenizer("");
			s = new BufferedReader (new FileReader(f));
		}
		
		public int nextInt() throws IOException{
			if(st.hasMoreTokens())
				return Integer.parseInt(st.nextToken());
			else{
				st = new StringTokenizer(s.readLine());
				return nextInt();
			}
		}
		
		public double nextDouble() throws IOException{
			if(st.hasMoreTokens())
				return Double.parseDouble(st.nextToken());
			else{
				st = new StringTokenizer(s.readLine());
				return nextDouble();
			}
		}
		
		public long nextLong() throws IOException{
			if(st.hasMoreTokens())
				return Long.parseLong(st.nextToken());
			else{
				st = new StringTokenizer(s.readLine());
				return nextLong();
			}
		}
		
		public String nextString() throws IOException{
			if(st.hasMoreTokens())
				return st.nextToken();
			else{
				st = new StringTokenizer(s.readLine());
				return nextString();
			}
			
		}
		public String readLine() throws IOException{
			return s.readLine();
		}
		
		public void close() throws IOException{
			s.close();
		}
		
	}
	
	////////////////////////////////////////////////////////////////////
	//		Number Theory
	
	public static int divisor(int x){
	    int limit = x;
	    int numberOfDivisors = 0;

	    for (int i=1; i < limit; ++i) {
	        if (x % i == 0) {
	            limit = x / i;
	            if (limit != i) {
	                numberOfDivisors++;
	            }
	            numberOfDivisors++;
	        }
	    }

	    return numberOfDivisors;
    }
	
	
	public static long gcd(long a, long b){
		return b == 0 ? a : gcd(b,a%b);
	}
	
  
	public static long lcm(long a,long b, long c){
		return lcm(lcm(a,b),c);
	}
	
	public static long lcm(long a, long b){
		return a*b/gcd(a,b);
	}
	
	
	////////////////////////////////////////////////////////////////////
	
	
//	  private static  	FastScanner s = new FastScanner(new File("input.txt"));
//	  private static PrintWriter ww = new PrintWriter(new FileWriter("output.txt"));
	  private static FastScanner s = new FastScanner();   
      private static PrintWriter ww = new PrintWriter(new OutputStreamWriter(System.out));
//    private static Scanner s = new Scanner(System.in);
      @SuppressWarnings("unused")
	private static Map<Integer,Integer> mm = new HashMap<Integer,Integer>();
      @SuppressWarnings("unused")
	private static Map<Integer,node> mn = new HashMap<Integer,node>();
	@SuppressWarnings("unused")
	private static int[][] states = { {-1,0} , {1,0} , {0,-1} , {0,1} };
	
      
    //////////////////////////////////////////////////////////////////// 
      
     static class node implements Comparable<node>{
      	int to;
      	int cost;
      	public node(int x, int y){
      		this.to  = x;
      		this.cost = y;
      	}
		@Override
		public int compareTo(node arg0) {
			// TODO Auto-generated method stub
			return Integer.compare(cost, arg0.cost);
		}
      }
     
     static class arrive{
    	 int[] arr;
    	 int i=0;
    	 public arrive(int n){
    		 arr = new int[n];
    	 }
    	 void set(int x){
    		 arr[i++] = x;
    	 }
     }
    
    public static void main(String[] args) throws IOException{
 		Solution so = new Solution();
 		so.solve();
 	}
   
    
    ////////////////////////////////////////////////////////////////////
     
   ArrayList<node>[] arr;
   boolean[] vis;
   arrive[] time;
   PriorityQueue<node> p;
   int[] dis;
    
   
   public static int[] prefixFunction(char[] pattern){
		
		int len = pattern.length;
		int k = 0;
		int[] pi = new int[len];
		pi[0] = 0;
		
		for(int i=1;i<len;i++){
			
			while(k > 0 && pattern[k] != pattern[i] )
				k = pi[k-1];
			if(pattern[k] == pattern[i])
				k ++;
			pi[i] = k;
		}
		return pi;
	}
   
     void solve() throws IOException{
    	
    	char[] patt = s.nextString().toCharArray();
 		int[] prefix = prefixFunction(patt);
 		int len = prefix.length;
 		int x = prefix[len-1];
 		int va = 0;
 		
 	//	for(int i: prefix) System.out.print(i+" ");
 		
 		
 		if(x == 0) ww.println("Just a legend");
 		else{
 			for(int i=0;i<len-1;i++){
 				if(prefix[i] == x)
 					va = 1;
 			}
 			if(va == 1 )
 				for(int i=0;i<x;i++) ww.print(patt[i]);
 			else{
 				if(prefix[prefix[len-1]-1] != 0){
 					int ll = prefix[prefix[len-1]-1];
 					for(int i=0;i<ll;i++) ww.print(patt[i]);
 				}else ww.println("Just a legend");
 			}
 		}
        s.close();
 	    ww.close(); 
    
     }
}