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

public class BetaRound93_Div1_B implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    public static void main(String[] args) {
        new Thread(null, new BetaRound93_Div1_B(), "", 256 * (1L << 20)).start();
    }

    public void run() {
        try {
            long t1 = System.currentTimeMillis();
            if (System.getProperty("ONLINE_JUDGE") != null) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            Locale.setDefault(Locale.US);
            solve();
            in.close();
            out.close();
            long t2 = System.currentTimeMillis();
            System.err.println("Time = " + (t2 - t1));
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    /** http://pastebin.com/j0xdUjDn */
    static class Utils {

        private Utils() {}

        public static void mergeSort(int[] a) {
            mergeSort(a, 0, a.length - 1);
        }

        private static final int MAGIC_VALUE = 50;

        private static void mergeSort(int[] a, int leftIndex, int rightIndex) {
            if (leftIndex < rightIndex) {
                if (rightIndex - leftIndex <= MAGIC_VALUE) {
                    insertionSort(a, leftIndex, rightIndex);
                } else {
                    int middleIndex = (leftIndex + rightIndex) / 2;
                    mergeSort(a, leftIndex, middleIndex);
                    mergeSort(a, middleIndex + 1, rightIndex);
                    merge(a, leftIndex, middleIndex, rightIndex);
                }
            }
        }

        private static void merge(int[] a, int leftIndex, int middleIndex, int rightIndex) {
            int length1 = middleIndex - leftIndex + 1;
            int length2 = rightIndex - middleIndex;
            int[] leftArray = new int[length1];
            int[] rightArray = new int[length2];
            System.arraycopy(a, leftIndex, leftArray, 0, length1);
            System.arraycopy(a, middleIndex + 1, rightArray, 0, length2);
            for (int k = leftIndex, i = 0, j = 0; k <= rightIndex; k++) {
                if (i == length1) {
                    a[k] = rightArray[j++];
                } else if (j == length2) {
                    a[k] = leftArray[i++];
                } else {
                    a[k] = leftArray[i] <= rightArray[j] ? leftArray[i++] : rightArray[j++];
                }
            }
        }

        private static void insertionSort(int[] a, int leftIndex, int rightIndex) {
            for (int i = leftIndex + 1; i <= rightIndex; i++) {
                int current = a[i];
                int j = i - 1;
                while (j >= leftIndex && a[j] > current) {
                    a[j + 1] = a[j];
                    j--;
                }
                a[j + 1] = current;
            }
        }

    }

    // solution

    final long PRIME1 = 31;
    final long PRIME2 = 57;
    
    int n;
    char[] s;
    long[] h1, h2, p1, p2;
    
    long hash1(int L, int R) {
        return (L == 0) ? h1[R] : h1[R] - h1[L-1];
    }
    
    long hash2(int L, int R) {
        return (L == 0) ? h2[R] : h2[R] - h2[L-1];
    }
    
    void solve() throws IOException {
        s = readString().toCharArray();
        n = s.length;
        p1 = new long[n+1];
        p1[0] = 1;
        for (int i = 1; i <= n; i++) {
            p1[i] = p1[i-1] * PRIME1;
        }
        p2 = new long[n+1];
        p2[0] = 1;
        for (int i = 1; i <= n; i++) {
            p2[i] = p2[i-1] * PRIME2;
        }
        h1 = new long[n];
        h1[0] = s[0] - 'a' + 1;
        for (int i = 1; i < n; i++) {
            h1[i] = h1[i-1] + p1[i] * (s[i] - 'a' + 1);
        }
        h2 = new long[n];
        h2[0] = s[0] - 'a' + 1;
        for (int i = 1; i < n; i++) {
            h2[i] = h2[i-1] + p2[i] * (s[i] - 'a' + 1);
        }
        int[] lengths = new int[n];
        int size = 0;
        for (int len = 1; len <= n-2; len++) {
            long prefixHash1 = hash1(0, len-1);
            long suffixHash1 = hash1(n-len, n-1);
            long prefixHash2 = hash2(0, len-1);
            long suffixHash2 = hash2(n-len, n-1);
            if (prefixHash1 * p1[n-len] == suffixHash1 && prefixHash2 * p2[n-len] == suffixHash2) {
                lengths[size++] = len;
            }
        }
        int L = 0, R = size - 1, mid = -1, pos = -1, ans = -1;
        while (L < R) {
            mid = (L + R) / 2;
            int len = lengths[mid];
            int res = check(len);
            if (res >= 0) {
                L = mid + 1;
                if (len > ans) {
                    pos = res;
                    ans = len;
                }
            } else {
                R = mid;
            }
        }
        for (int i = max(0, L-1); i <= min(size-1, R+1); i++) {
            int len = lengths[i];
            int res = check(len);
            if (res >= 0) {
                if (len > ans) {
                    pos = res;
                    ans = len;
                }
            }
        }
        if (pos == -1) {
            out.println("Just a legend");
            return;
        }
        for (int i = pos; i < pos + ans; i++) {
            out.print(s[i]);
        }
        out.println();
    }
    
    int check(int len) {
        long prefixHash1 = hash1(0, len-1);
        long suffixHash1 = hash1(n-len, n-1);
        long prefixHash2 = hash2(0, len-1);
        long suffixHash2 = hash2(n-len, n-1);
        if (prefixHash1 * p1[n-len] != suffixHash1 || prefixHash2 * p2[n-len] != suffixHash2) {
            return -1;
        }
        for (int start = 1; start + len < n; start++) {
            long h1 = hash1(start, start+len-1);
            long h2 = hash2(start, start+len-1);
            if (h1 == prefixHash1 * p1[start] && h2 == prefixHash2 * p2[start]) {
                return start;
            }
        }
        return -1;
    }

}