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.*;
import java.util.*;
public final class password
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static long[] pow1,pow2,inv1,inv2;
	static long mod1=(long)(1e9+7),mod2=(long)(1e9+9),base=37;
	static int maxn=(int)(1e6+1);
	static List<Integer> list=new ArrayList<Integer>();
	static long[] hash1,hash2;
	
	static long pow(long a,long b,long mod)
	{
		long x=1,y=a;
		while(b>0)
		{
			if(b%2==1)
			{
				x=(x*y)%mod;
			}
			y=(y*y)%mod;
			b=b/2;
		}
		return x;
	}
	
	static long mod_inv(long a,long mod)
	{
		return pow(a,mod-2,mod);
	}
	
	public static void main(String args[]) throws Exception
	{
		pow1=new long[maxn];pow2=new long[maxn];pow1[0]=pow2[0]=1;inv1=new long[maxn];inv2=new long[maxn];inv1[0]=inv2[0]=1;
		for(int i=1;i<maxn;i++)
		{
			pow1[i]=(pow1[i-1]*base)%mod1;
			pow2[i]=(pow2[i-1]*base)%mod2;
		}
		inv1[maxn-1]=mod_inv(pow1[maxn-1],mod1);inv2[maxn-1]=mod_inv(pow2[maxn-1],mod2);
		for(int i=maxn-2;i>=0;i--)
		{
			inv1[i]=(inv1[i+1]*base)%mod1;
			inv2[i]=(inv2[i+1]*base)%mod2;
		}
		// finished all preprocessing...
		char[] a=sc.next().toCharArray();long curr1=0,curr2=0,curr3=0,curr4=0;hash1=new long[a.length];hash2=new long[a.length];
		for(int i=0,j=0,k=a.length-1;i<a.length;i++,j++,k--)
		{
			curr1=(curr1+((a[i]-'a'+1)*pow1[j]))%mod1;
			curr1=(curr1%mod1+mod1)%mod1;
			curr2=(curr2+((a[i]-'a'+1)*pow2[j]))%mod2;
			curr2=(curr2%mod2+mod2)%mod2;
			curr3=(curr3*base)%mod1;
			curr3=(curr3%mod1+mod1)%mod1;
			curr3=(curr3+(a[k]-'a'+1))%mod1;
			curr3=(curr3%mod1+mod1)%mod1;
			curr4=(curr4*base)%mod2;
			curr4=(curr4%mod2+mod2)%mod2;
			curr4=(curr4+(a[k]-'a'+1))%mod2;
			curr4=(curr4%mod2+mod2)%mod2;
			if(curr1==curr3 && curr2==curr4)
			{
				list.add(i+1);
			}	
			hash1[i]=curr1;hash2[i]=curr2;
		}
		if(list.size()>1)
		{
			int low=0,high=list.size()-1;
			while(low<high)
			{
				int mid=(low+high+1)>>1,val=list.get(mid);boolean curr=false;
				long now1=hash1[val-1],now2=hash2[val-1];
				for(int i=1;i+val-1<a.length-1;i++)
				{
					long ll1=(hash1[i+val-1]-hash1[i-1])%mod1;
					ll1=(ll1%mod1+mod1)%mod1;
					ll1=(ll1*inv1[i])%mod1;
					ll1=(ll1%mod1+mod1)%mod1;
					long ll2=(hash2[i+val-1]-hash2[i-1])%mod2;
					ll2=(ll2%mod2+mod2)%mod2;
					ll2=(ll2*inv2[i])%mod2;
					ll2=(ll2%mod2+mod2)%mod2;
					if(ll1==now1 && ll2==now2)
					{
						curr=true;
						break;
					}
				}
				if(curr)
				{
					low=mid;
				}
				else
				{
					high=mid-1;
				}
			}
			int val=list.get(low);boolean b=false;
			long now1=hash1[val-1],now2=hash2[val-1];
			for(int i=1;i+val-1<a.length-1;i++)
			{
				long ll1=(hash1[i+val-1]-hash1[i-1])%mod1;
				ll1=(ll1%mod1+mod1)%mod1;
				ll1=(ll1*inv1[i])%mod1;
				ll1=(ll1%mod1+mod1)%mod1;
				long ll2=(hash2[i+val-1]-hash2[i-1])%mod2;
				ll2=(ll2%mod2+mod2)%mod2;
				ll2=(ll2*inv2[i])%mod2;
				ll2=(ll2%mod2+mod2)%mod2;
				if(ll1==now1 && ll2==now2)
				{
					b=true;
					break;
				}
			}
			if(b)
			{
				for(int i=0;i<list.get(low);i++)	
				{
					out.print(a[i]);
				}
				out.println("");
			}
			else
			{
				out.println("Just a legend");
			}
		}
		else
		{
			out.println("Just a legend");
		}
		out.close();
	}
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}