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.*;
import java.io.*;
import java.math.*;
public class Main {
	public static long mod= (long) (1e9 +7);
	public static void main(String args[])
	{
		InputReader s= new InputReader(System.in);
		OutputStream outputStream= System.out;
		PrintWriter out= new PrintWriter(outputStream);
		String str= s.next();
		int n= str.length();
		int[] p = prefixFunction(str);
		if(p[n-1]==0){
			System.out.println("Just a legend");
			return;
		}
		int flag=0;
		for(int i=0;i<n-1;i++){
			if(p[i]==p[n-1]){
				flag=1;
				break;
			}
		}
		StringBuilder temp1= new StringBuilder();
		//String temp="";
		for(int i=1;i<=p[n-1];i++){
			temp1.append(str.charAt(n-p[n-1]+i-1));
			//temp+= str.charAt(n-p[n-1]+i-1);
		}
		if(flag==1){
			System.out.println(temp1);
			return;
		}
		int next[]= prefixFunction(temp1.toString());
		if(next[p[n-1]-1]==0){
			System.out.println("Just a legend");	
		}
		else{
			int b= next[p[n-1]-1];
			StringBuilder x= new StringBuilder();
		//	String x="";
			for(int i=1;i<=b;i++){
				x.append(str.charAt(n-b+i-1));
			//	x+= str.charAt(n-b+i-1);
			}
			out.println(x);
		}
		
		
		
		out.close();
	}
	public static int[] prefixFunction(String s) {
	    int[] p = new int[s.length()];
	    int k = 0;
	    for (int i = 1; i < s.length(); i++) {
	      while (k > 0 && s.charAt(k) != s.charAt(i))
	        k = p[k - 1];
	      if (s.charAt(k) == s.charAt(i))
	        ++k;
	      p[i] = k;
	    }
	    return p;
	  }

	  public static int kmpMatcher(String s, String pattern) {
	    int m = pattern.length();
	    if (m == 0)
	      return 0;
	    int[] p = prefixFunction(pattern);
	    for (int i = 0, k = 0; i < s.length(); i++)
	      for (; ; k = p[k - 1]) {
	        if (pattern.charAt(k) == s.charAt(i)) {
	          if (++k == m)
	            return i + 1 - m;
	          break;
	        }
	        if (k == 0)
	          break;
	      }
	    return -1;
	  }
	  
	static long combinations(long n,long r){   // O(r)
		if(r==0 || r==n) return 1;
		r= Math.min(r, n-r);
		long ans=n;  // nC1=n;
		for(int i=1;i<r;i++){
			ans= ans*(n-i);
			ans= ans/(i+1);
		}
		return ans;
		
	}
	public static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
	static long modulo(long a,long b,long c) {
		long x=1;
		long y=a;
		while(b > 0){
			if(b%2 == 1){
				x=(x*y)%c;
			}
			y = (y*y)%c; // squaring the base
			b /= 2;
		}
		return  x%c;
	}
	static void catalan_numbers(int n) {
		long catalan[]= new long[n+1];
	    catalan[1] = 1;
	    for (int i = 2; i <= n; i++) {
	        for (int j = 1; j <= i - 1; j++) {
	            catalan[i] = catalan[i] + ((catalan[j]) * catalan[i - j]);
	        }
	    }
	}
	
	static ArrayList<Integer> primeFactors(int n)   // O(sqrt(n))
	{
	    // Print the number of 2s that divide n
		ArrayList<Integer> arr= new ArrayList<>();
	    while (n%2 == 0)
	    {
	        arr.add(2);
	        n = n/2;
	    }
	 
	    // n must be odd at this point.  So we can skip one element (Note i = i +2)
	    for (int i = 3; i <= Math.sqrt(n); i = i+2)
	    {
	        // While i divides n, print i and divide n
	        while (n%i == 0)
	        {
	            arr.add(i);
	            n = n/i;
	        }
	    }
	    // This condition is to handle the case when n is a prime number
	    // greater than 2
	    if (n > 2)
	        arr.add(n);
	    
	    return arr;
	}

	public static long expo(long a, long b){
		if (b==0)
	        return 1%mod;
	    if (b==1)
	        return a%mod;
	    if (b==2)
	        return ((a%mod)*(a%mod))%mod;

	    if (b%2==0){
	            return expo(expo(a%mod,(b%mod)/2)%mod,2%mod)%mod;
	    }
	    else{
	        return (a%mod)*(expo(expo(a%mod,(b-1)%mod/2)%mod,2%mod)%mod)%mod;
	    }
	}
	static class Pair implements Comparable<Pair>
	{
		long f;
		String s;
		Pair(long ii, String cc)
		{
			f=ii;
			s=cc;
		}
		
		public int compareTo(Pair o) 
		{
			return Long.compare(this.f, o.f);
		}
		
	}
	
	public static int[] sieve(int N){    // O(n*log(logn))
		int arr[]= new int[N+1];
		for(int i=2;i<=Math.sqrt(N);i++){
			if(arr[i]==0){
				for(int j= i*i;j<= N;j= j+i){
					arr[j]=1;
				}
			}
		}
		return arr;
		// All the i for which arr[i]==0 are prime numbers.
	}
	static long gcd(long a,long b){       // O(logn)
		if(b==0) return a;
		return gcd(b,a%b);
	}
	static class InputReader {

	    public BufferedReader reader;
	    public StringTokenizer tokenizer;
 
	    public InputReader(InputStream inputstream) {
	      reader = new BufferedReader(new InputStreamReader(inputstream));
	      tokenizer = null;
	    }
	    
	    public String nextLine(){
	    	String fullLine=null;
	    	while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	            try {
	              fullLine=reader.readLine();
	            } catch (IOException e) {
	              throw new RuntimeException(e);
	            }
	            return fullLine;
	          }
	          return fullLine;
	    }
		public String next() {
	      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
	        try {
	          tokenizer = new StringTokenizer(reader.readLine());
	        } catch (IOException e) {
	          throw new RuntimeException(e);
	        }
	      }
	      return tokenizer.nextToken();
	    }
		public long nextLong() {
		      return Long.parseLong(next());
		    }
	    public int nextInt() {
	      return Integer.parseInt(next());
	    }
	  }
}