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.*;
import java.io.*;
public class A
{
      public static void main(String ar[]) throws Exception
      {
            BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
            String S=br.readLine();
            char c[]=S.toCharArray();
            int n=c.length;
            int a[]=new int[n];
            int j=0,i=1;
            while(i<n)
            {
                  while(j>0 && c[i]!=c[j])
                   j=a[j-1];
                  if(c[i]==c[j])
                  {
                        a[i]=j+1;
                        j++;
                  }
                  i++;
            }
            
            HashSet<Integer> hs=new HashSet<Integer>();
            for(int k=1;k<n-1;k++)
             hs.add(a[k]);
            
            j=a[n-1];
            int u=-1;
            //System.out.println(Arrays.toString(a));
            while(j>0)
            {
              if(hs.contains(j))
              { u=j; break; }
              j=a[j-1];
            }
            
            if(u>0)
             System.out.println(S.substring(0,j));
            else
             System.out.println("Just a legend");
      }
}