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:
// Created by Whiplash99
import java.io.*;
import java.util.*;
public class B
{
    private static final int p=31, m=(int)(1e9)+9;
    private static int lim;
    private static long pow[], hash[];
    private static char str[];

    private static void calc_pow()
    {
        pow[0]=1;
        for(int i=1;i<lim;i++)
            pow[i]=(pow[i-1]*p)%m;
    }
    private static long rollingH()
    {
        long ans=0;
        for(int i=0;i<lim;i++)
            ans=hash[i]=(ans+((str[i]-'a'+1)*pow[i])%m)%m;
        return ans;
    }
    private static long rangeH(int i, int j)
    {
        return (i==0)?hash[j]:(hash[j]-hash[i-1]+m)%m;
    }
    private static int solve(int s1, int s2, int N, int flag)
    {
        int l=0,r=N-1,mid,ans=0;
        long rH1,rH2;

        while(l<=r)
        {
            mid=l+((r-l)>>1);
            rH1=(rangeH(s1,s1+mid)*pow[lim-s1-1])%m;

            if(flag==1)
                rH2=(rangeH(lim-mid-1,lim-1)*pow[mid])%m;
            else
                rH2=(rangeH(s2,s2+mid)*pow[lim-s2-1])%m;

            if(rH1==rH2)
                l=ans=mid+1;
            else
                r=mid-1;
        }
        return ans;
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,N,ans=0;

        str=br.readLine().trim().toCharArray();
        lim=str.length;
        pow=new long[lim];
        hash=new long[lim];
        calc_pow();
        rollingH();

        for(i=1;i<lim-1;i++)
            ans=Math.max(ans,solve(0,i,lim-i-1,0));
        for(;ans>0;ans--)
        {
            if((rangeH(0,ans-1)*pow[lim-1])%m==(rangeH(lim-ans,lim-1)*pow[ans-1])%m)
                break;
        }

        StringBuilder sb=new StringBuilder();
        for(i=0;i<ans;i++)
            sb.append(str[i]);
        if(sb.length()==0)
            sb.append("Just a legend");

        System.out.println(sb);
    }
}