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

public class D {

	private D (Scanner sc) throws Throwable {
		String input = sc.next();
		solve(input);
	}
	
	private void solve (String input) throws Throwable {
		int N = input.length();
		int [] Z = zFunction(input.toCharArray());

		boolean [] SF = new boolean [N];
		boolean [] MD = new boolean [N];
		
		for (int i = 0; i < N; ++i) {
			if (Z[i] > 0) {
				if (i + Z[i] == N)
					SF[Z[i]] = true;
				if (i > 0) {
					if (Z[i] > 1 && i + Z[i] == N)
						MD[Z[i]-1] = true;
					if (i + Z[i] < N)
						MD[Z[i]] = true;
				}
			}
		}
		
		for (int i = N-1; i > 0; --i) 
			if (MD[i]) {
				for (int j = 1; j < i; ++j)
					MD[j] = true;
				break;
			}
		
		for (int i = N-1; i > 0; --i)
			if (SF[i] && MD[i]) {
				print(input.substring(0, i));
				return;
			}
		
		print ("Just a legend");
	}

	int [] zFunction(char [] C) {
		int [] F = new int [C.length];
		int L = 0, R = 1;
		for (int i = 1; i < C.length; ++i) {
			if (i < R) {
				F[i] = Math.min(F[i-L], R-i);
				if (F[i] == R-i)
					for (int j = 0; R+j < C.length && C[R+j] == C[R-i+j]; ++j, ++F[i]);
			} else
				for (int j = 0; i+j < C.length && C[i+j] == C[j]; ++j, ++F[i]);

			if (F[i] >= R-i) {
				L = i;
				R = i + F[i];
			}
		}		
		return F;		
	}

	////////////////////////////////////////////////////////////////////////////////////

	private void print (Object o) {
		System.out.println(o);
	}
	
	public static void main(String[] args) throws Throwable {		
		Scanner sc = new Scanner(System.in);
		new D(sc);
	}	
}