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 password {

	static class kmp {

		static char[] T, P;
		static int n, m, f[];

		static void preprocess() {
			n = T.length;
			m = P.length;
			int i = 0, j = -1;
			f = new int[P.length + 1];

			f[0] = -1;
			while (i < m) {
				// System.out.println("once");
				while (j >= 0 && P[i] != P[j]) {
					j = f[j];

				}
				f[++i] = ++j;
				System.out.println(i + " " + j);

				// System.out.println(i+" "+j+" "+P.length);
			}
			System.out.println("done");
		}

		static void search() {
			int i = 0, j = 0;
			while (i < n) {
				while (j >= 0 && T[i] != P[j])
					j = f[j];
				i++;
				j++;
				if (j == m) {
					System.out.printf("P is found at index %d in T\n", i - j);
					j = f[j];
				}
			}

		}

		// Prefix Function: pi[k] = length of longest proper prefix matching a
		// suffix ending at k
		static int[] prefixFunction(char[] s) // O(n)
		{
			int n = s.length, pi[] = new int[n];
			for (int i = 1, j = 0; i < n; ++i) // j = pi[i-1] at the beginning
												// of every iteration
			{
				while (j > 0 && s[i] != s[j])
					j = pi[j - 1];
				if (s[i] == s[j])
					++j;
				pi[i] = j;
			}
			return pi;
		}

	}

public static void main(String[] args) {
	Scanner sc=new Scanner(System.in);
	String x=sc.next();
	kmp k=new kmp();
	int [] prefix=k.prefixFunction(x.toCharArray());
	int val=0;
	val=prefix[prefix.length-1];
	
	String s=x.substring(prefix.length-val, prefix.length);
	int [] prefix2=k.prefixFunction(s.toCharArray());
	int size=0;
	if(prefix2.length!=0)size=prefix2[prefix2.length-1];
//	System.out.println("hell");
	if(size==0)
	size=val;
	boolean found=false;
//	System.out.println(val);
	for (int i = 0; i < prefix.length-1; i++) {
		if(prefix[i]==val){
			size=val;
			found=true;
			break;
		}if(prefix[i]==size){
			found=true;
			
		}
	}
//	System.out.println("hell");
	if(found&&size!=0)
		System.out.println(s.substring(0, size));
	else System.out.println("Just a legend");
}
}