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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Stack;

public class ProblemB {
	
	static final long PRM = 1000000009; 
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);

		
		char[] line = in.readLine().toCharArray();
		int len = line.length;
		
		long[] prmp = new long[len+1];
		prmp[0] = 1;
		for (int i = 1 ; i <= len ; i++) {
			prmp[i] = prmp[i-1] * PRM;
		}

		
		long[] prehash = new long[len+1];
		long[] sufhash = new long[len+1];
		for (int i = 0 ; i < len ; i++) {
			prehash[i+1] = prehash[i];
			prehash[i+1] *= PRM;
			prehash[i+1] += line[i];
		}
		for (int i = 0 ; i < len ; i++) {
			sufhash[i+1] = sufhash[i];
			sufhash[i+1] += prmp[i] * line[len-i-1];
		}
		
		int max = 0;
		for (int k = len - 2 ; k >= 1 ; k--) {
			if (prehash[k] == sufhash[k]) {
				int head = 1;
				int tail = 1+k;
				long hash = 0;
				for (int u = 1 ; u < tail ; u++) {
					hash += prmp[k-u] * line[u];
				}
				
				if (hash == prehash[k]) {
					max = k;
					break;
				}
				
				boolean found = false;
				while (tail < len-1) {
					hash *= PRM;
					hash -= prmp[k] * line[head];
					hash += line[tail];
					tail++;
					head++;
					if (hash == prehash[k]) {
						found = true;
						break;
					}
				}
				if (found) {
					max = k;
					break;
				}
			}
		}
		
		if (max == 0) {
			out.println("Just a legend");
		} else {
			out.println(String.valueOf(line).substring(0, max));
		}
		out.flush();
	}
	
	
	public static void debug(Object... o) {
		System.err.println(Arrays.deepToString(o));
	}
}