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 java.awt.*;
import java.math.*;

public class Main {
	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out) );
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st = new StringTokenizer("");
	static String next() throws Exception {

		while (!st.hasMoreTokens()) {
			String s = br.readLine();
			if (s == null)
				return null;
			st = new StringTokenizer(s);
		}
		return st.nextToken();
	}

	public static void main(String[] asda) throws Exception {

	//	int CASES = Integer.parseInt( next() );
		String s = next();
		int Z [] = Z( s );
		
		int N = Z.length;
		
		int max = 0;
		int len = 0;
		for (int i = 1; i < N; i++)	{
			if	( N - i == Z[i] && max >= N - i )	{
				// suffix
				len = N - i;
				break;
			}
			max = Math.max(max, Z[i] );
		}
		
		out.println( len == 0 ? "Just a legend" : s.substring(0, len) );
		
		//
		out.flush();
		System.exit(0);
	}
	static int [] Z(String s)	{
		int N = s.length();
		int L, R;
		int Z [] = new int [N];
		
		L = R = 0;
		for (int i = 1; i < N; i++)	{
			
			if	( i > R )	{
				L = R = i;
				while	( R < N && s.charAt(R - L) == s.charAt(R) )
					R++;
				Z[i] = R-- - L;
				continue;
			}
			
			int k = i - L;
			if	( Z[k] < R - i + 1 )	{
				Z[i] = Z[k];
				continue;
			}
			
			L = i;
			while	( R < N && s.charAt(R - L) == s.charAt(R) )
				R++;
			Z[i] = R-- - L;
			
		}
		return	Z;
	}
	
}

/**
 * 1 12 3 3 5 3 1 2 10 5 3 8 6 4
**/