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 org.omg.PortableInterceptor.INACTIVE;

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


public class Solution {

    class KMP {

        String pattern, sb;
        int[] prefix;

        KMP(String pattern, String sb) {
            this.pattern = pattern;
            this.sb = sb;
            fillPrefix();
        }

        private void fillPrefix() {
            int patlen = pattern.length();
            prefix = new int[pattern.length()];
            prefix[0] = 0;
            int k = 0;
            int ind = 1;
            while (ind < patlen) {
                if (pattern.charAt(ind) == pattern.charAt(k)) {
                    k++;
                    prefix[ind] = k;
                    ind++;
                } else {
                    if (k != 0)
                        k = prefix[k - 1];
                    else {
                        prefix[ind] = 0;
                        ind++;
                    }
                }
            }
        }

        void kmp() {

            int tlen = sb.length();
            int plen = pattern.length();
            int counter = 0;

            int tind = 0;
            int pind = 0;
            while (tind < tlen) {
                if (pattern.charAt(pind) == sb.charAt(tind)) {
                    tind++;
                    pind++;
                }
                if (pind == plen) {
                    counter++;
                    pind = prefix[pind - 1];
                } else if (tind < tlen && pattern.charAt(pind) != sb.charAt(tind)) {
                    if (pind != 0)
                        pind = prefix[pind - 1];
                    else
                        tind++;
                }
            }
        }
    }

    Kattio io = new Kattio(System.in, System.out);
    KMP kmp;
    String word, res;
    int[] prefArr;

    Solution() {
        word = io.getWord();
        kmp = new KMP(word, word);
        prefArr = kmp.prefix;
        int n = prefArr.length;
        int prefSufComLen = prefArr[n - 1];
        res = "Just a legend";

        for (int i = 0; i < n; i++) {
            //System.out.println(i + " : " + prefArr[i]);
        }
        boolean alternative1 = compareAgainstLastCell(prefSufComLen, n);
        if (!alternative1) {
            alternative2(prefSufComLen, n);
        }
        io.println(res);

        io.close();
    }


    private void alternative2(int prefSufComLen, int n) {
        if (prefSufComLen == 0)
            return;
        int len = prefArr[prefSufComLen - 1];
        if (len > 0)
            res = word.substring(0, len);
    }


    private boolean compareAgainstLastCell(int prefSufComLen, int n) {
        if (prefSufComLen == 0) return false;

        for (int i = 1; i < n - 1; i++) {
            if (prefArr[i] == prefSufComLen) {
                res = word.substring(0, prefSufComLen);
                return true;
            }
        }

        return false;
    }


    public static void main(String[] args) {
        new Solution();
    }
}


/**
 * Simple yet moderately fast I/O routines.
 * <p>
 * Example usage:
 * <p>
 * Kattio io = new Kattio(System.in, System.out);
 * <p>
 * while (io.hasMoreTokens()) {
 * int n = io.getInt();
 * double d = io.getDouble();
 * double ans = d*n;
 * <p>
 * io.println("Answer: " + ans);
 * }
 * <p>
 * io.close();
 * <p>
 * <p>
 * Some notes:
 * <p>
 * - When done, you should always do io.close() or io.flush() on the
 * Kattio-instance, otherwise, you may lose output.
 * <p>
 * - The getInt(), getDouble(), and getLong() methods will throw an
 * exception if there is no more data in the input, so it is generally
 * a good idea to use hasMoreTokens() to check for end-of-file.
 *
 * @author: Kattis
 */

class Kattio extends PrintWriter {
    public Kattio(InputStream i) {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(i));
    }

    public Kattio(InputStream i, OutputStream o) {
        super(new BufferedOutputStream(o));
        r = new BufferedReader(new InputStreamReader(i));
    }

    public boolean hasMoreTokens() {
        return peekToken() != null;
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }

    public String getLine() {
        try {
            return r.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return null;
    }


    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) {
                e.printStackTrace();
            }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }
}