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.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
public class Main{
    public static void main(String[]args){
        InputStream in = System.in;
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        try{
//          in = new BufferedInputStream(new FileInputStream(new File("input.txt")));
//          out = new PrintWriter(new BufferedOutputStream(new FileOutputStream("output.txt")));
        }catch (Exception e) {
        }
        new Main().run(in,out);
        out.flush();
    }
    private void debug(Object...os){
        System.err.println(deepToString(os));
    }
    
    private void run(InputStream in,PrintWriter out){
        String s=next(in) + '$';
        int[] sa=suffixArray(s);
        int[] as=new int[sa.length];
        for(int i=0;i<sa.length;i++){
            as[sa[i]]=i;
        }
        int[] lcp=calcLCP(sa,s);
        int[] len=new int[sa.length];
        len[as[0]] = s.length();
        for(int i=as[0]+1;i<sa.length;i++){
            len[i]=min(len[i-1],lcp[i-1]);
        }
        for(int i=as[0]-1;i>=0;i--){
            len[i]=min(len[i+1],lcp[i]);
        }
        int res = -1;
        for(int i=sa.length-2;i>=1;i--){
            int t = sa.length-1-i;
            int id = as[t];
            boolean ok=false;
            if(len[id]>=i){
//              debug(as[0],id);
                if(abs(as[0]-id)>1){
                    ok=true;
                }else{
                    int mn=min(as[0],id);
                    int mx=max(as[0],id);
                    if(mn-1>=0 && len[mn-1]>=i)ok=true;
                    if(mx+1<len.length && len[mx+1]>=i)ok=true;
                }
            }
            if(ok){
                res=i;break;
            }
        }
        System.out.println(res==-1 ? "Just a legend" : s.substring(0,res));
    }
    
    public int[] calcLCP(int[] SA,String s) {
        if(SA.length != s.length())throw new IllegalArgumentException();
        int n = s.length();
        int[] rank=new int[n];// s[i..] がSAにおいて何番目か.
        for(int i=0;i<n;i++)rank[SA[i]]=i;
        int[] lcp=new int[n-1];
        for(int i=0,h=0;i<n;i++)if(rank[i]<n-1) {
            while(s.charAt(i+h) == s.charAt(SA[rank[i]+1]+h))h++;
            lcp[rank[i]]=h;
            if(h>0)h--;
        }
        return lcp;
    }
    
    public int[] suffixArray(String s) {
        int n = s.length();
        for(int i=0;i<n-1;i++)if(s.charAt(i) <= s.charAt(n-1))
            throw new IllegalArgumentException("last character must be sentinel.");
        boolean[] ex=new boolean[256];
        int numLetter = 0;
        for(int i=0;i<n;i++) {
            char c = s.charAt(i);
            if(!ex[c])numLetter++;
            ex[c]=true;
        }
        int[] id=new int[256];
        numLetter=0;
        for(int i=0;i<256;i++)if(ex[i])id[i]=numLetter++;
        int[] is=new int[n];
        for(int i=0;i<n;i++)is[i]=id[s.charAt(i)];
        int[] SA = suffixArray(is,numLetter);
        return SA;
    }

    private int[] suffixArray(int[] a,final int numLetter){
        int n=a.length;
        if(numLetter==n) {
            int[] res=new int[n];
            for(int i=0;i<n;i++)res[a[i]]=i;
            return res;
        }
        int[] to=new int[numLetter];
        int[] head=new int[numLetter];// staticにおいてもいい.
        int[] tail=new int[numLetter];// staticにおいてもいい.
        for(int i=0;i<n;i++)to[a[i]]++;
        for(int i=0;i<numLetter-1;i++)to[i+1]+=to[i];
        for(int i=0;i<numLetter;i++)head[i]=i==0?0:to[i-1];
        System.arraycopy(to,0,tail,0,numLetter);

        boolean[] S_Type=new boolean[n];
        S_Type[n-1]=true;
        int numLMS=0;
        for(int i=n-2;i>=0;i--) {
            if(a[i]<a[i+1] || a[i]==a[i+1] && S_Type[i+1])S_Type[i]=true;
            if(!S_Type[i] && S_Type[i+1])numLMS++;
        }
        int[] SA=new int[n];
        Arrays.fill(SA,-1);
        int[] i2LMS=new int[n];
        int[] LMS2i=new int[numLMS];
        for(int i=n-1,j=numLMS;i>=1;i--)if(i==n-1 || S_Type[i] && !S_Type[i-1]) {// i : LMS
            i2LMS[i]=--j;
            LMS2i[j]=i;
            SA[--tail[a[i]]] = i;
        }
        // step2
        for(int i=0;i<n;i++)if(SA[i]>0 && !S_Type[SA[i]-1]) {
            SA[head[a[SA[i]-1]]++] = SA[i]-1;
        }
        System.arraycopy(to,0,tail,0,numLetter);
        // step3
        for(int i=n-1;i>=0;i--)if(SA[i]>0 && S_Type[SA[i]-1]) {
            SA[--tail[a[SA[i]-1]]] = SA[i]-1;
        }
        // construct a1
        int[] a1=new int[numLMS];
        int numLet1=-1;
        for(int i=0,bef=-1;i<n;i++)if(SA[i]>0 &&  S_Type[SA[i]] && !S_Type[SA[i]-1]) {// SA1[i] : LMS
            boolean same=true;
            if(bef==-1)same=false;
            else {
                int tmp = i2LMS[SA[i]];// LMS id
                if(bef==numLMS-1 || tmp==numLMS-1 || LMS2i[bef+1]-LMS2i[bef] != LMS2i[tmp+1]-LMS2i[tmp]) {
                    same=false;
                }else {
                    for(int j=0;j<LMS2i[bef+1]-LMS2i[bef];j++) {
                        if(a[LMS2i[bef] + j] != a[LMS2i[tmp] + j] || S_Type[LMS2i[bef] + j] != S_Type[LMS2i[tmp] + j]) {
                            same=false;break;
                        }
                    }
                }
            }
            if(same)a1[i2LMS[SA[i]]]=numLet1;
            else {
                bef=i2LMS[SA[i]];// LMS id
                a1[i2LMS[SA[i]]]=++numLet1;
            }
        }
        numLet1++;
        int[] SA1 = suffixArray(a1,numLet1);// i -> i-th substr id

        // reuse SA,head,tail
        Arrays.fill(SA,-1);
        for(int i=0;i<numLetter;i++)head[i]=i==0?0:to[i-1];
        System.arraycopy(to,0,tail,0,numLetter);

        // step1
        for(int lms=numLMS-1;lms>=0;lms--) {
            int i=LMS2i[SA1[lms]];
            SA[--tail[a[i]]] = i;
        }
        // step2
        for(int i=0;i<n;i++)if(SA[i]>0 && !S_Type[SA[i]-1]) {
            SA[head[a[SA[i]-1]]++] = SA[i]-1;
        }
        // step3
        System.arraycopy(to,0,tail,0,numLetter);
        for(int i=n-1;i>=0;i--)if(SA[i]>0 && S_Type[SA[i]-1]) {
            SA[--tail[a[SA[i]-1]]] = SA[i]-1;
        }
        return SA;
    }
    
    private String next(InputStream in) {
        try {
            StringBuilder res = new StringBuilder("");
            int c = in.read();
            while (Character.isWhitespace(c))
                c = in.read();
            do {
                res.append((char) c);
            } while (!Character.isWhitespace(c = in.read()));
            return res.toString();
        } catch (Exception e) {
            return null;
        }
    }

    private int nextInt(InputStream in){
        try{
            int c=in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextInt(in);
            int res=0;
            do{
                res*=10;
                res+=c-'0';
                c=in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
    
    private long nextLong(InputStream in){
        try{
            int c=in.read();
            if(c==-1) return c;
            while(c!='-'&&(c<'0'||'9'<c)){
                c=in.read();
                if(c==-1) return c;
            }
            if(c=='-') return -nextLong(in);
            long res=0;
            do{
                res*=10;
                res+=c-'0';
                c=in.read();
            }while('0'<=c&&c<='9');
            return res;
        }catch(Exception e){
            return -1;
        }
    }
}