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:
/**
 * Created by icon on 1/17/2016.
 */

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.StringTokenizer;


public class CF126B {
    public static void main(String[] args) {
        InputStream input = System.in;
        OutputStream output = System.out;
        Reader in = new Reader(input);
        PrintWriter out = new PrintWriter(output);
        Task magician = new Task();
        magician.solve(in, out);
        out.close();
    }

    static class Task {
        final int MOD = 1000000007;
        final int MOD2 = 1500450271;
        final int BASE = 1022201;
        final int BASE2 = 1178711;
        long [] E, E2, H, H2;
        int size;
        public void solve(Reader in, PrintWriter out) {
            String str = in.next();
            size = str.length();

            E = new long[size + 1]; E2 = new long[size + 1];
            H = new long[size + 1]; H2 = new long[size + 1];
            E[0] = E2[0] = 1L;
            H[0] = H2[0] = 0L;

            for(int i = 1; i <= size; i++) {
                E[i] = (E[i - 1] * BASE) % MOD;
                E2[i] = (E2[i - 1] * BASE2) % MOD2;
                H[i] = (H[i - 1] * BASE + str.charAt(i - 1)) % MOD;
                H2[i] = (H2[i - 1] * BASE2 + str.charAt(i - 1)) % MOD2;
            }

            ArrayList<Integer> positions = new ArrayList<>();

            for(int i = 1; i < size; i++) {
                if(match(i)) {
                    positions.add(i);
                }
            }

            // for(int i : positions) out.print(i + " ");

            int left = 0, right = positions.size() - 1;
            int res = -1;
            while(left <= right) {
                int mid = (left + right) >> 1;
                if(okay(positions.get(mid))) {
                    res = positions.get(mid);
                    left = mid + 1;
                } else right = mid - 1;
            }
            if(res == -1) out.print("Just a legend");
            else out.print(str.substring(0, res));
        }

        boolean match(int pos) {
            long beg = H[pos], beg2 = H2[pos];
            int last = size - pos;
            // System.out.println(pos + " " + last);
            long end = (H[size] - (H[last] * E[pos]) % MOD + MOD) % MOD;
            long end2 = (H2[size] - (H2[last] * E2[pos]) % MOD2 + MOD2) % MOD2;
            return (beg == end && beg2 == end2);
        }

        boolean okay(int pos) {
            long cur = H[pos], cur2 = H2[pos];
            for(int i = pos + 1; i < size; i++) {
                long now = (H[i] - (H[i - pos] * E[pos]) % MOD + MOD) % MOD;
                long now2 = (H2[i] - (H2[i - pos] * E2[pos]) % MOD2 + MOD2) % MOD2;
                if(cur == now && cur2 == now2) return  true;
            }
            return  false;
        }
    }

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

        public Reader(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 int nextInt() {
            return Integer.parseInt(next());
        }

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

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