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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        long startTime = System.nanoTime();
        solve();
        long endTime = System.nanoTime();
        err.println("Execution Time : +" + (endTime - startTime) / 1000000 + " ms");
        exit(0);
    }

    static void solve() {
        String s = in.next();
        long[] pow = new long[1000010];
        final long HASH = 3137;
        pow[0] = 1;
        for (int i = 1; i < pow.length; i++) {
            pow[i] = pow[i - 1] * HASH;
        }
        long[] hash = new long[s.length() + 1];
        for (int i = 0; i < s.length(); i++) {
            hash[i + 1] = hash[i] * HASH + s.charAt(i);
        }
        ArrayList<Integer> valid = new ArrayList<>();
        for (int len = 1; len <= s.length() - 2; len++) {
            long prefix = hash[len];
            long suffix = hash[s.length()] - hash[s.length() - len] * pow[len];
            if (prefix == suffix) {
                valid.add(len);
            }
        }
        int min = -1;
        int max = valid.size() - 1;
        while (min != max) {
            int mid = (min + max) / 2;
            if (min == mid) {
                mid++;
            }
            int len = valid.get(mid);
            boolean can = false;
            for (int k = 1; !can && k + len < s.length(); k++) {
                long curr = hash[k + len] - hash[k] * pow[len];
                can = curr == hash[len];
            }
            if (can) {
                min = mid;
            } else {
                max = mid - 1;
            }
        }
        if(min == -1)
            out.println("Just a legend");
        else
            out.println(s.substring(0,valid.get(min)));
    }

    static void solveBKP() {
        String s = in.next();
        String y = StringUtils.constructStringFromChars(s.toCharArray(), 0, s.length() - 1);
        String z = StringUtils.constructStringFromChars(ArrayUtils.reverse(s.toCharArray()), 0, s.length() - 1);
        int[] pi = StringUtils.prefix_function(y.toCharArray());
        int[] si = StringUtils.prefix_function(z.toCharArray());
        out.println(Arrays.toString(pi));
        out.println(Arrays.toString(si));
        int max_so_far = 0;
        int n = s.length();
        int ans = 0;
        if (ans > 0) {
            out.println(StringUtils.constructStringFromChars(s.toCharArray(), 0, ans));
        } else {
            out.println("Just a legend");
        }
    }

    static class StringUtils {
        static char[] constructReverseWithHash(String s) {
            char[] a = s.toCharArray();
            char[] b = ArrayUtils.reverse(s.toCharArray());
            char[] c = new char[a.length + b.length + 1];
            System.arraycopy(a, 0, c, 0, a.length);
            c[a.length] = '#';
            System.arraycopy(b, 0, c, a.length + 1, b.length);
            return c;
        }

        static String reverse(String s) {
            return constructStringFromChars(ArrayUtils.reverse(s.toCharArray()), 0, s.length());
        }

        static String constructStringFromChars(char[] d, int from, int to) {
            StringBuilder res = new StringBuilder();
            for (int i = from; i < to; i++) {
                res.append(d[i]);
            }
            return res.toString();
        }

        static String constructStringFromInts(int[] d, int from, int to) {
            StringBuilder res = new StringBuilder();
            for (int i = from; i < to; i++) {
                res.append(d[i]);
            }
            return res.toString();
        }

        static int[] prefix_function(char[] s) {
            int n = s.length;
            int[] pi = new int[n];
            for (int i = 1; i < n; i++) {
                int j = pi[i - 1];
                while (j > 0 && s[i] != s[j])
                    j = pi[j - 1];
                if (s[i] == s[j]) {
                    j++;
                }
                pi[i] = j;
            }
            return pi;
        }
    }

    static class NumberTheory {

        static ArrayList<Integer>[] getDivisors(int n) {
            ArrayList<Integer>[] d = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) {
                d[i] = new ArrayList<>();
            }
            for (int i = 1; i <= n; i++) {
                for (int j = i; j <= n; j += i) {
                    d[j].add(i);
                }
            }
            return d;
        }

        static long mod_pow(long x, long y, long MOD) {
            if (y == 0) {
                return 1;
            }
            if (y == 1) {
                return x;
            }
            long v = mod_pow(x, y / 2, MOD);
            if ((y & 1) > 0) {
                return v * v % MOD * x % MOD;
            }
            return v * v % MOD;
        }

        static int gcd(int a, int b) {
            while (b != 0) {
                int t = b;
                b = a % b;
                a = t;
            }
            return a;
        }

        //GCD Long
        static long gcd(long a, long b) {
            while (b != 0) {
                long t = b;
                b = a % b;
                a = t;
            }
            return a;
        }

    }

    static class ArrayUtils {

        static int[] reverse(int[] data) {
            int[] p = new int[data.length];
            for (int i = 0, j = data.length - 1; i < data.length; i++, j--) {
                p[i] = data[j];
            }
            return p;
        }

        static char[] reverse(char[] data) {
            char[] p = new char[data.length];
            for (int i = 0, j = data.length - 1; i < data.length; i++, j--) {
                p[i] = data[j];
            }
            return p;
        }

        static int[] MegreSort(int[] A) {
            if (A.length > 1) {
                int q = A.length / 2;
                int[] left = new int[q];
                int[] right = new int[A.length - q];
                System.arraycopy(A, 0, left, 0, q);
                System.arraycopy(A, q, right, 0, A.length - q);
                int[] left_sorted = MegreSort(left);
                int[] right_sorted = MegreSort(right);
                return Megre(left_sorted, right_sorted);
            } else {
                return A;
            }
        }

        static int[] Megre(int[] left, int[] right) {
            int[] A = new int[left.length + right.length];
            int i = 0;
            int j = 0;
            for (int k = 0; k < A.length; k++) {
                // To handle left becoming empty
                if (i == left.length && j < right.length) {
                    A[k] = right[j];
                    j++;
                    continue;
                }
                // To handle right becoming empty
                if (j == right.length && i < left.length) {
                    A[k] = left[i];
                    i++;
                    continue;
                }
                if (left[i] <= right[j]) {
                    A[k] = left[i];
                    i++;
                } else {
                    A[k] = right[j];
                    j++;
                }
            }
            return A;
        }

        static long[] MegreSort(long[] A) {
            if (A.length > 1) {
                int q = A.length / 2;
                long[] left = new long[q];
                long[] right = new long[A.length - q];
                System.arraycopy(A, 0, left, 0, q);
                System.arraycopy(A, q, right, 0, A.length - q);
                long[] left_sorted = MegreSort(left);
                long[] right_sorted = MegreSort(right);
                return Megre(left_sorted, right_sorted);
            } else {
                return A;
            }
        }

        static long[] Megre(long[] left, long[] right) {
            long[] A = new long[left.length + right.length];
            int i = 0;
            int j = 0;
            for (int k = 0; k < A.length; k++) {
                // To handle left becoming empty
                if (i == left.length && j < right.length) {
                    A[k] = right[j];
                    j++;
                    continue;
                }
                // To handle right becoming empty
                if (j == right.length && i < left.length) {
                    A[k] = left[i];
                    i++;
                    continue;
                }
                if (left[i] <= right[j]) {
                    A[k] = left[i];
                    i++;
                } else {
                    A[k] = right[j];
                    j++;
                }
            }
            return A;
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

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

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public int[] readAllInts(int n) {
            int[] p = new int[n];
            for (int i = 0; i < n; i++) {
                p[i] = in.nextInt();
            }
            return p;
        }

        public int[] readAllInts(int n, int s) {
            int[] p = new int[n + s];
            for (int i = s; i < n + s; i++) {
                p[i] = in.nextInt();
            }
            return p;
        }

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

    static void exit(int a) {
        out.close();
        err.close();
        System.exit(a);
    }

    static InputStream inputStream = System.in;
    static OutputStream outputStream = System.out;
    static OutputStream errStream = System.err;
    static InputReader in = new InputReader(inputStream);
    static PrintWriter out = new PrintWriter(outputStream);
    static PrintWriter err = new PrintWriter(errStream);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

}