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

public class B126 {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		String s = bf.readLine();
		HashSet<Integer> set = new HashSet<>();
		int[] freq = new int[(int)1e6+1];
		
		int[] z = z(s.toCharArray());
		
		int val = -1;
		int i = z.length-1;
		for(i = z.length-1;i>=1;i--)
		{
			freq[z[i]]++;
			val = Math.max(val, z[i]);
			if(z[i]==s.length()-i)
				set.add(z[i]);
		}
		
		for(i = val;i>=1;i--)
			if(freq[i]>(i==val?1:0)&set.contains(i))
			{
				System.out.println(s.substring(s.length()-i));
				return;
			}
		
		System.out.println("Just a legend");
	}
	static int[] z(char[] str)
	{
		int[] Z = new int[str.length];
	    int n = str.length;
	    int L, R, k;
	 
	    // [L,R] make a window which matches with prefix of s
	    L = R = 0;
	    for (int i = 1; i < n; ++i)
	    {
	        // if i>R nothing matches so we will calculate.
	        // Z[i] using naive way.
	        if (i > R)
	        {
	            L = R = i;
	 
	            // R-L = 0 in starting, so it will start
	            // checking from 0'th index. For example,
	            // for "ababab" and i = 1, the value of R
	            // remains 0 and Z[i] becomes 0. For string
	            // "aaaaaa" and i = 1, Z[i] and R become 5
	            while (R<n && str[R-L] == str[R])
	                R++;
	            Z[i] = R-L;
	            R--;
	        }
	        else
	        {
	            // k = i-L so k corresponds to number which
	            // matches in [L,R] interval.
	            k = i-L;
	 
	            // if Z[k] is less than remaining interval
	            // then Z[i] will be equal to Z[k].
	            // For example, str = "ababab", i = 3, R = 5
	            // and L = 2
	            if (Z[k] < R-i+1)
	                 Z[i] = Z[k];
	 
	            // For example str = "aaaaaa" and i = 2, R is 5,
	            // L is 0
	            else
	            {
	                //  else start from R  and check manually
	                L = i;
	                while (R<n && str[R-L] == str[R])
	                    R++;
	                Z[i] = R-L;
	                R--;
	            }
	        }
	    }
	    return Z;
	}
}