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.math.BigInteger;
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] ;
        }

        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;
        }
    }
    class Hashing
    {
        final byte [] P = {31 , 43} ;
        final int [] MOD = {(int)1e9 + 9 , (int)1e9 + 7} ;
        final int [] modInv = {BigInteger.valueOf(P[0]).modInverse(BigInteger.valueOf(MOD[0])).intValue() , BigInteger.valueOf(P[1]).modInverse(BigInteger.valueOf(MOD[1])).intValue()} ;
        int [][] hash , inv;
        
        Hashing(char [] s)
        {
            int n = s.length;
            hash = new int [2][n + 1] ;
            inv = new int [2][n + 1] ;
            inv[0][0] = inv[1][0] = 1 ;

            int [] pow = new int [2] ;
            pow[0] = pow[1] = 1 ;

            for(int i = 1 ; i <= n ; i++)
            {
                int c = s[i - 1] - 'a' + 1 ;
                for(int j = 0 ; j < 2 ; j ++)
                {
                    hash[j][i] = (int)((1L * hash[j][i - 1] + (1L * c * pow[j]) % MOD[j]) % MOD[j]) ;
                    inv[j][i] = (int)(1L * inv[j][i - 1] * modInv[j] % MOD[j]) ;
                    pow[j] = (int)(1L * pow[j] * P[j] % MOD[j]) ;
                }
            }
        }
        long getHash(int i , int j)
        {
            long high = ((hash[1][j] - hash[1][i - 1] + 1L * MOD[1]) * 1L * inv[1][i - 1] )% MOD[1] ;
            long low = ((hash[0][j] - hash[0][i - 1] + 1L * MOD[0]) * 1L * inv[0][i - 1] )% MOD[0] ;
            return (high << 32) | 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();}

}