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 static java.lang.Math.* ;
import static java.util.Arrays.* ;

import java.util.*;
import java.io.*;

public class Main
{
    void main() throws Exception
    {
        Scanner sc = new Scanner(System.in) ;
        PrintWriter out = new PrintWriter(System.out) ;
        String s = sc.next() ;
        char [] a = s.toCharArray() ;
        SuffixAutomaton sa = new SuffixAutomaton(a) ;
        Hashing hashing = new Hashing(a) ;
        int state = 0 ;
        int ans = -1 ;
        for(int l = 0 ; l < a.length ; l++)
        {
            int r = a.length - l - 1 ;
            state = sa.next[a[l] - 'a'][state] ;
            if(hashing.getHash(1 , l + 1) == hashing.getHash(r + 1, a.length) && sa.cnt[state] >= 3)
                ans = l + 1 ;
        }
        if(ans != -1)
            out.println(s.substring(0 , ans));
        else
            out.println("Just a legend");
        out.flush();
        out.close();
    }
    class SuffixAutomaton
    {
        int[] link, len , cnt;
        int [][] next ;
        boolean [] isClone ;
        int lst, idx;

        SuffixAutomaton(char[] s)
        {
            int n = s.length;
            link = new int[n<<1];
            len = new int[n<<1];
            next = new int [26][n << 1] ;
            cnt = new int [n << 1] ;
            isClone = new boolean[n << 1] ;
            for(char c: s)
                addLetter(c - 'a');

            for(int v = idx ;  v > 0 ; v -- )
                if(!isClone[v])
                    cnt[link[v]] += cnt[v] ;
            for(int v = idx ;  v > 0 ; v -- )
                if(isClone[v])
                    cnt[link[v]] += cnt[v] ;
//            link = null ;
//            isClone = null ;
//            len = null ;

        }

        void addLetter(int c)
        {
            int cur = ++idx, p = lst;
            while(next[c][p] == 0) { next[c][p] = cur; p = link[p]; }
            cnt[cur] = 1 ;
            int q = next[c][p];
            if(q != cur)
                if(len[q] == len[p] + 1)
                    link[cur] = q;
                else
                {
                    int clone = ++idx;
                    isClone[clone] = true ;
                    len[clone] = len[p] + 1;
                    link[clone] = link[q];
                    for(int i = 0 ; i < 26 ; i++)
                        next[i][clone] = next[i][q] ;
                    link[cur] = link[q] = clone;
                    while(next[c][p] == q) { next[c][p] =  clone; p = link[p]; }
                }
            len[cur] = len[lst] + 1;
            lst = cur;
        }
    }
    int pow(int a , int e , int MOD)
    {
        int res = 1 ;
        while(e > 0)
        {
            if((e & 1) == 1)
                res = (int)(1L * res * a % MOD) ;
            a = (int)(1L * a * a % MOD) ;
            e >>= 1 ;
        }
        return res ;
    }
    class Hashing
    {
        final byte P_L = 31 , P_H = 43;
        final  int MOD_L = (int)1e9 + 9 , MOD_INV_L =  pow(P_L, MOD_L - 2, MOD_L);
        final int MOD_H = (int)1e9 + 7 , MOD_INV_H =  pow(P_H, MOD_H - 2, MOD_H);
        int [] hash_LOW  , hash_HIGH;
        int [] inv_LOW  , inv_HIGH;
        int n ;

        Hashing(char [] s)
        {
            n = s.length;
            hash_LOW = new int [n + 1];
            hash_HIGH = new int [n + 1] ;
            inv_LOW = new int [n + 1] ;
            inv_HIGH = new int [n + 1] ;
            inv_LOW[0] = inv_HIGH[0] = 1;

            long pow_L  = 1 ;
            long pow_H  = 1 ;

            for(int i = 1 ; i <= n ; i++)
            {
                int c = s[i - 1] - 'a' + 1 ;

                hash_LOW[i] = (int) (((1L * hash_LOW[i - 1] + (1L * c * pow_L)) % MOD_L) % MOD_L);
                inv_LOW[i] = (int)(1L * inv_LOW[i - 1] * MOD_INV_L % MOD_L);
                pow_L = (int)(1L * pow_L * P_L % MOD_L);

                hash_HIGH[i] = (int)((1L * hash_HIGH[i - 1] + (1L * c * pow_H % MOD_H))% MOD_H) ;
                inv_HIGH[i] = (int)(1L * inv_HIGH[i - 1] * MOD_INV_H % MOD_H);
                pow_H = (int)(1L * pow_H * P_H % MOD_H);
            }

        }
        long getHash(int i , int j)
        {

            long get_HIGH = ((hash_HIGH[j] - hash_HIGH[i - 1] + 1L * MOD_H) * 1L * inv_HIGH[i - 1] )% MOD_H ;
            long get_LOW = ((hash_LOW[j] - hash_LOW[i - 1] + 1L * MOD_L) * 1L * inv_LOW[i - 1] )% MOD_L ;
            return (get_HIGH << 32) | get_LOW ;

        }
    }
    class Scanner
    {
        BufferedReader br;
        StringTokenizer st;

        Scanner(InputStream in)
        {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        Scanner(String path) throws Exception
        {
            br = new BufferedReader(new FileReader(path)) ;
        }
        String next() throws Exception
        {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }
        int nextInt() throws Exception { return Integer.parseInt(next()); }

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

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

    public static void main (String [] args) throws Exception {(new Main()).main();}

}