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.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class a {
	public static void main(String[] Args) throws Exception {
		FS sc = new FS(System.in);
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		String s = sc.next();
		int[] x = genZValues(s);
        int mid = 0;
        int n = x.length;
        int ans = 0;
        for (int i = 1; i < n; i++){
            if (x[i] > ans && i + x[i] == n && mid >= x[i]){
                ans = x[i];
            }
            if (x[i] > mid && i + x[i] != n) {
                mid = x[i];
            } else if (x[i] - 1 > mid && i + x[i] == n) {
                mid = x[i] - 1;
            }
        }
        if (ans == 0){
            out.println("Just a legend");
        } else {
            out.println(s.substring(0, ans));
        }
		out.close();
	}

    public static int[] genZValues(String s) {
        int[] z = new int[s.length()];
        for(int i=1,g=0,f=0,N=s.length(); i<N; i++)
            if(i<g && z[i-f]!=g-i)
                z[i] = Math.min(z[i-f],g-i);
            else for(g=g>(f=i)?g:f,z[i]=g-f;g<N && s.charAt(g)==s.charAt(z[i]); g++,z[i]++);
        return z;
    }
    
	public static class IntervalTree {
		static final int NULL_VALUE = -1; // change this
		int[] lo, hi, carry, val;

		public IntervalTree(int N) {
			lo = new int[4 * (N + 1)];
			hi = new int[4 * (N + 1)];
			carry = new int[4 * (N + 1)];
			val = new int[4 * (N + 1)];
			init(1, 0, N - 1);
		}

		public void set(int l, int h, int v) {
			set(1, l, h, v);
		}

		public int query(int l, int h) {
			return query(1, l, h);
		}

		private int aggregate(int x, int y) {
			return Math.max(x, y);
		}

		private void init(int i, int l, int h) {
			lo[i] = l;
			hi[i] = h;
			if (l == h)
				return;
			int m = (l + h) / 2;
			init(2 * i, l, m);
			init(2 * i + 1, m + 1, h);
		}

		private void set(int i, int l, int h, int v) {
			if (l <= lo[i] && hi[i] <= h) {
				carry[i] = v;
				val[i] = v;
			}
			else if (l <= hi[i] && lo[i] <= h) {
				push(i);
				set(2 * i, l, h, v);
				set(2 * i + 1, l, h, v);
			}
		}

		private int query(int i, int l, int h) {
			if (h < lo[i] || hi[i] < l)
				return NULL_VALUE;
			if (l <= lo[i] && hi[i] <= h)
				return val[i];
			push(i);
			return aggregate(query(2 * i, l, h), query(2 * i + 1, l, h));
		}

		private void push(int i) {
			if (carry[i] == 0)
				return;
			set(2 * i, lo[2 * i], hi[2 * i], carry[i]);
			set(2 * i + 1, lo[2 * i + 1], hi[2 * i + 1], carry[i]);
			carry[i] = 0;
		}
	}

	public static class Pair implements Comparable<Pair> {
		int x, y;

		Pair(int a, int b) {
			x = a;
			y = b;
		}

		public int compareTo(Pair o) {
			if (x == o.x)
				return o.y - y;
			return o.x - x;
		}

		public String toString() {
			return x + " " + y;
		}
	}

	public static class FS {
		BufferedReader br;
		StringTokenizer st;

		FS(InputStream in) throws Exception {
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer(br.readLine());
		}

		FS(File f) throws Exception {
			br = new BufferedReader(new FileReader(f));
			st = new StringTokenizer(br.readLine());
		}

		String next() throws Exception {
			if (st.hasMoreTokens())
				return st.nextToken();
			st = new StringTokenizer(br.readLine());
			return next();
		}

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

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

		double nextDouble() throws Exception {
			return Double.parseDouble(next());
		}
	}
}
/*
 * 
 * 19 2 2 2 2 2 2 2 2 1 1 1 2 1 1 2 1 1 1 2
 * 
 * 
 */