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-20); i <= min(size-1, R+20); 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;
	}

}