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.Arrays;
import java.util.Scanner;

public class Password3 
{

	public static void main(String[] args) 
	{
		String s;
		Scanner sc = new Scanner(System.in);
		
		s = sc.next();
		
		int j = 0;
		boolean debug = false;
		int[] a = new int[1000000];
		{
		int i = 1;
		if(debug)System.out.print(" ");
		
		int streak1 = 0;
		while(i<=s.length()-1)
		{
//			System.out.println("ij " + i + " " + j);
			if(s.charAt(i) == s.charAt(j))
			{
				j++;
				a[i] = j;
//				System.out.println(a[i]);
				i++;
			}
			else
			{
				if(j == 0)
				{
					i++;
				}
				else
				{
					j = a[j-1]; //should actually go to array;
//					System.out.println("j went to a[i-1] " + (i-1));
				}
			}
		}
		if(debug)System.out.print("\n");
		}
		
		if(debug)
		{
			for(int i = 0; i < s.length(); i++)
			{
				System.out.print(i%10);
			}
			if(debug)System.out.print("\n");
		
			for(int i = 0; i < s.length(); i++)
			{
				System.out.print(a[i]%10);
			}
			if(debug)System.out.print("\n");
		}
		
		int n = s.length()-1;
		int times = 0;
		
		if(a[n] == 0)
		{
			System.out.println("Just a legend");
			return;
		}

		for(int i0 = 0; i0 < s.length() ; i0++)
		{
			if(a[i0] == a[n] && i0 != n)
			{
				if(debug)System.out.println(a[n] + " " + n);
				System.out.println(s.substring(0, a[n]));
				return;
			}
		}
		if(a[a[n]-1] > 0)
		{
			System.out.println(s.substring(0, a[a[n]-1]));
			return;
		}
		else
		{
			System.out.println("Just a legend");
			return;
		}

	}

}