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.util.Scanner;

public class PrefixSubstrSuffix {

    String wordStr;
    public static void main(String[] args) {
        PrefixSubstrSuffix myp = new PrefixSubstrSuffix();
        myp.run();
    }

    public void run(){
        Scanner in = new Scanner(System.in);

        wordStr = in.nextLine();
        char[] word = wordStr.toCharArray();
        in.close();

        int[] prefixMatch = new int[word.length];
        int left = -1;
        int right = -1;
        int longestNonSuffMatch = -1;
        for (int i = 1; i < word.length; i++) {
            if (i <= right) {
                int maxExtension = right - i + 1;
                int prefixVal = prefixMatch[i - left];
                prefixMatch[i] = Math.min(maxExtension, prefixVal);
            }
            while (prefixMatch[i] + i < word.length && word[i + prefixMatch[i]] == word[prefixMatch[i]]) {
                prefixMatch[i]++;
            }
            if (i > right) {
                left = i;
                right = i + prefixMatch[i] - 1;
            }

            // check if suffix match else check if longest
            if (i + prefixMatch[i] == word.length) {
                if (longestNonSuffMatch > 0 && longestNonSuffMatch >= prefixMatch[i]) {
                    finish(prefixMatch[i]);
                    return;
                }
            }
            longestNonSuffMatch = Math.max(longestNonSuffMatch, prefixMatch[i]);
        }
        System.out.println("Just a legend");
    }

    public void finish(int n) {
        if (n > 0) {
            System.out.println(wordStr.substring(0, n));
        } else {
            System.out.println("Just a legend");
        }
    }
}