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.*;
import java.math.BigInteger;
import java.util.*;

/**
 *
 * @author Saju
 *
 */

public class Main {

	static int[] dx = { 0, 1, 0, -1, -1, 1, 1, -1 };
	static int[] dy = { -1, 0, 1, 0, -1, -1, 1, 1 };

	static int[] kx = { 2, 1, -1, -2, -2, -1, 1, 2 };
	static int[] ky = { 1, 2, 2, 1, -1, -2, -2, -1 };

	static final int MOD = 10007;
	static final int MAX = 50000;
	static long INF = Long.MAX_VALUE;

	public static void main(String[] args) {

		InputReader in = new InputReader(System.in);

		
//		int n = in.nextInt();
//		int a = in.nextInt();
//		int b = in.nextInt();
//		int c = in.nextInt();
		
//		int f[] = new int[n + 1];
//		f[0] = 0;
//		f[1] = 0;
//		f[2] = 0;
//		
//		for(int i = 3; i <= n; i++){
//			f[i] = ((a % MOD * f[i - 1] % MOD) % MOD + (b % MOD * f[i - 3] % MOD) % MOD + c % MOD) % MOD;
//		}
//		System.out.println(f[n]);
		
//		text = "abcdabc";
//		pattern = "abcdabc";
		text = in.next();
		pattern = String.valueOf(text);
		
		String val = kmpSearch();
		if(val == null){
			System.out.println("Just a legend");
		}
		else{
			System.out.println(val);
		}
		
		System.exit(0);
	}

	static int[] prefixTable = new int[1000005];
	   
    static String text = "";
    static String pattern = "";
   
    
	 private static String  kmpSearch() {
	       
	        kmpPreprocess();
	       
	       
//	        int i = 0, j = 0;
//	        while (i < n) {
//	            while (j >= 0 && text.charAt(i) != pattern.charAt(j))
//	                j = prefixTable[j];
//	            i++;
//	            j++;
//	        }
//	        return j;
	        
	        int n = text.length(); 
	        
	        // If lps of n-1 is zero 
	        if (prefixTable[n - 1] == 0) 
	        { 
//	            System.out.println(-1); 
	            return null; 
	        } 
	        for (int i = 0; i < n - 1; i++)  
	        { 
	      
	            // At any position lps[i] equals to lps[n - 1] 
	            if (prefixTable[i] == prefixTable[n - 1])  
	            { 
//	                System.out.println(text.substring(0, prefixTable[i] + 1)); 
	                return text.substring(0, prefixTable[i]); 
	            } 
	        } 
	      
	        // If answer is not possible 
//	        System.out.println(prefixTable[n - 1]);
//	        if(prefixTable[n - 1] <= 0){
//	        	return null;
//	        }
	        if (prefixTable[prefixTable[n - 1] - 1] == 0) {
//	            System.out.println(-1); 
	        	return null;
	        }
	        else{
//	            System.out.println(text.substring(0, prefixTable[prefixTable[n - 1] - 1] + 1)); 
	       
	        	
	            return text.substring(0, prefixTable[prefixTable[n - 1] - 1]);
	        }
	    }
	 
	 private static void kmpPreprocess() {
	       
//	        int i = 0, j = -1;
//	        prefixTable[i] = j;
//	        int n = pattern.length();
//	        while (i < n) {
//	            while (j >= 0 && pattern.charAt(i) != pattern.charAt(j))
//	                j = prefixTable[j];
//	            i++;
//	            j++;
//	            prefixTable[i] = j;
//	        }
		 
		 int n = pattern.length(); 
	      
	        // To store longest prefix suffix 
//	        int [] lps = new int [n]; 
	      
	        // Length of the previous 
	        // longest prefix suffix 
	        int len = 0; 
	      
	        // lps[0] is always 0 
	        prefixTable[0] = 0; 
	        int i = 1; 
	      
	        // Loop calculates lps[i] for i = 1 to n - 1 
	        while (i < n)  
	        { 
	            if (pattern.charAt(i) == pattern.charAt(len))  
	            { 
	                len++; 
	                prefixTable[i] = len; 
	                i++; 
	            } 
	      
	            // (pat[i] != pat[len]) 
	            else 
	            { 
	                if (len != 0) 
	                    len = prefixTable[len - 1]; 
	                // Also, note that we do not increment 
	                // i here 
	      
	                // If len = 0 
	                else
	                { 
	                    prefixTable[i] = 0; 
	                    i++; 
	                } 
	            } 
	        } 
	    }
	

	// nCk
	// private static long binomialCoeff(int n, int k){
	// long[] arr = new long[k + 1];
	// arr[0] = 1;
	// for(int i = 1; i <= n; i++){
	// for(int j = Math.min(i, k); j > 0; j--){
	// arr[j] = (arr[j] + arr[j - 1]) % MOD;
	// }
	// }
	// return arr[k];
	// }

	// BIT =>
	// https://www.hackerearth.com/practice/notes/binary-indexed-tree-or-fenwick-tree/
	// static int BIT[] = new int[MAX + 5];
	//
	// private static int query(int index) {
	// int sum = 0;
	// for (; index > 0; index -= (index & (-index))) {
	// sum += BIT[index];
	// }
	// return sum;
	// }
	//
	// private static void update(int size, int index, int val) {
	// for (; index <= size; index += (index & (-index))) {
	// BIT[index] += val;
	// }
	// }

	/*
	 * 
	 * tutorial :
	 * https://helloacm.com/algorithms-series-0-1-backpack-dynamic-programming-
	 * and-backtracking/
	 * 
	 */

	// here arr and prob zero based index
	// static int backPack(int n, int m, int[] arr, double[] prob, double p) {
	// double dp[][] = new double[n + 1][m + 1];
	// for (int i = 0; i <= n; ++i) {
	// dp[i][0] = 1.0;
	// }
	// for (int i = 1; i <= n; i++) {
	// for (int j = 1; j <= m; j++) {
	//
	// if (j < arr[i - 1]) { // insufficient capacity
	// dp[i][j] = dp[i - 1][j];
	// } else {
	// dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - arr[i - 1]] * (1.0 -
	// prob[i - 1]));
	// }
	//
	// }
	// }
	// for (int i = m; i >= 0; i--) { // reverse checking the maximum weight
	// if ((1.0 - dp[n][i]) <= p) {
	// return i;
	// }
	// }
	// return 0;
	// }

	// here arr and prob one based index
	// static int backPack1(int n, int m, int[] arr, double[] prob, double p) {
	//
	// double dp[] = new double[m + 1];
	//
	// dp[0] = 1.0;
	// for (int i = 1; i <= n; i++) {
	// for (int j = m; j >= arr[i]; --j) {
	// // dp[j] = dp[j] || dp[j - A[i - 1]];
	// dp[j] = Math.max(dp[j], dp[j - arr[i]] * (1.0 - prob[i]));
	// }
	// }
	// for (int i = m; i >= 0; i--) {
	// if (1.0 - dp[i] <= p) {
	// return i;
	// }
	// }
	// return 0;
	// }

	/*
	 *
	 * tutorial :
	 * https://www.hackerearth.com/practice/algorithms/searching/ternary-search/
	 * tutorial/
	 *
	 */

	// lightoj -> 1146
	// static double ternary(Point a, Point b, Point c, Point d) {
	//
	// double l = 0;
	// double r = 1;
	//
	// for (int i = 0; i < 200; i++) {
	// double mid1 = l + ((r - l) / 3);
	// double mid2 = r - ((r - l) / 3);
	//
	// double dis1 = func(a, b, c, d, mid1);
	// double dis2 = func(a, b, c, d, mid2);
	//
	// if(dis1 > dis2){
	// l = mid1;
	//
	// }
	// else{
	// r = mid2;
	// }
	// }
	//
	// return l;
	//
	// }
	//
	// static double func(Point a, Point b, Point c, Point d, double multiple) {
	//
	// double xDifAB = b.x - a.x;
	// double yDifAB = b.y - a.y;
	// double xDifCD = d.x - c.x;
	// double yDifCD = d.y - c.y;
	//
	// double x1 = a.x + xDifAB * multiple;
	// double y1 = a.y + yDifAB * multiple;
	// double x2 = c.x + xDifCD * multiple;
	// double y2 = c.y + yDifCD * multiple;
	//
	// double distance = Math.sqrt(((x1 - x2) * (x1 - x2)) +
	// ((y1 - y2) * (y1 - y2)));
	//
	// return distance;
	// }
	//
	// static class Point{
	// double x;
	// double y;
	//
	// Point(double x, double y){
	// this.x = x;
	// this.y = y;
	// }
	// }

	// static void primeFactorization(int n) {
	// int temp = n;
	// Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	// for (int i = 2; i <= Math.sqrt(n); i++) {
	// if (n % i == 0) {
	// int count = 0;
	// while (n % i == 0) {
	// count++;
	// n = n / i;
	// }
	// System.out.println("i: " + i + ", count: " + count);
	// map.put(i, count);
	// }
	//
	// }
	// if (n != 1) {
	// System.out.println(n);
	// map.put(n, 1);
	// }
	//
	//// calculateSumOfDivisor(map, temp);
	// }

	// static int counter[] = new int[MAX];
	//
	// private static void calculateSumOfDivisor(Map<Integer, Integer> map, int
	// n) {
	// int sum = 1;
	// for(Integer key : map.keySet()){
	// int count = map.get(key);
	// sum *= ((Math.pow(key, count + 1) - 1) / (key - 1));
	// }
	// if(sum < MAX){
	// if(counter[sum] < n){
	//// System.out.println("H");
	// counter[sum] = n;
	// }
	//
	// }
	//
	//// System.out.println(sum);
	// }

	// static int phi[] = new int[MAX];
	// static int phiStepCount[] = new int[MAX];
	// static void computeTotient() {
	//
	// // Create and initialize an array to store
	// // phi or totient values
	// for (int i = 1; i < MAX; i++) {
	// phi[i] = i; // indicates not evaluated yet
	// // and initializes for product
	// // formula.
	// }
	//
	// // Compute other Phi values
	// for (int p = 2; p < MAX; p++) {
	//
	// // If phi[p] is not computed already,
	// // then number p is prime
	// if (phi[p] == p) {
	//
	// // Phi of a prime number p is
	// // always equal to p-1.
	// phi[p] = p - 1;
	//
	// // Update phi values of all
	// // multiples of p
	// for (int i = 2 * p; i < MAX; i += p) {
	//
	// // Add contribution of p to its
	// // multiple i by multiplying with
	// // (1 - 1/p)
	// phi[i] = (phi[i] / p) * (p - 1);
	// }
	//
	// // for (int i = p; i < MAX; i += p) {
	// //
	// // phi[i] -= (phi[i] / p);
	// // }
	//
	// }
	// phiStepCount[p] = phiStepCount[phi[p]] + 1;
	// }
	//
	// for(int i = 1; i < MAX; i++){
	// phiStepCount[i] += phiStepCount[i - 1];
	// }
	// }

	// public static BigInteger floorOfNthRoot(BigInteger x, int n) {
	// int sign = x.signum();
	// if (n <= 0 || (sign < 0))
	// throw new IllegalArgumentException();
	// if (sign == 0)
	// return BigInteger.ZERO;
	// if (n == 1)
	// return x;
	// BigInteger a;
	// BigInteger bigN = BigInteger.valueOf(n);
	// BigInteger bigNMinusOne = BigInteger.valueOf(n - 1);
	// BigInteger b = BigInteger.ZERO.setBit(1 + x.bitLength() / n);
	// do {
	// a = b;
	// b = a.multiply(bigNMinusOne).add(x.divide(a.pow(n - 1))).divide(bigN);
	// } while (b.compareTo(a) == -1);
	// return a;
	// }

	// O(log(max(A, B))).
	// static long gcd(long a, long b) {
	// if (b == 0)
	// return a;
	// return gcd(b, a % b);
	// }

	// private static double getDistance(double x1, double y1, double x2, double
	// y2) {
	//
	// return Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2);
	// }

	// private static int getDecimal(String str) {
	// int val = 0;
	//
	// for (int i = str.length() - 1, j = 0; i >= 0; i--, j++) {
	// if (str.charAt(i) == '1') {
	// val += Math.pow(2, j);
	// }
	// }
	// return val;
	// }

	// private static int call(int i, int j, int[][] colors) {
	//
	// if (i >= colors.length) {
	// return 0;
	// }
	//
	// if (dp[i][j] != -1) {
	// return dp[i][j];
	//
	// }
	//
	// int result = Integer.MAX_VALUE;
	//
	// for (int k = 0; k < 3; k++) {
	// if (k == j) {
	// continue;
	// } else {
	// result = Math.min(result, call(i + 1, k, colors) + colors[i][j]);
	// }
	// }
	//
	// return dp[i][j] = result;
	// }

	static int dp[][];

	// private static BigInteger fac(int n, int mod) {
	//
	// if (n <= 0) {
	// return BigInteger.ONE;
	// }
	// return BigInteger.valueOf(n).multiply(fac(n - 1, mod));
	// }

	// private static long modInverse(long n, long m){
	// return bigMod(n, m - 2, m);
	// }

	// private static long bigMod(long n, long k, long m) {
	//
	// long ans = 1;
	// while (k > 0) {
	// if ((k & 1) == 1) {
	// ans = (ans * n) % m;
	// }
	// n = (n * n) % m;
	// k >>= 1;
	// }
	// return ans;
	// }

	// Returns an iterator pointing to the first element
	// in the range [first, last] which does not compare less than val.
	// private static int lowerBoundNew(long[] arr, long num){
	// int start = 0;
	// int end = arr.length - 1;
	// int index = 0;
	// int len = arr.length;
	// int mid = 0;
	// while(true){
	// if(start > end){
	// break;
	// }
	// mid = (start + end) / 2;
	// if(arr[mid] > num){
	// end = mid - 1;
	// }
	// else if(arr[mid] < num){
	// start = mid + 1;
	// }
	// else{
	// while(mid >= 0 && arr[mid] == num){
	// mid--;
	// }
	// return mid + 1;
	// }
	// }
	// if(arr[mid] < num){
	// return mid + 1;
	// }
	// return mid;
	// }

	// upper_bound() is a standard library function
	// in C++ defined in the header .
	// It returns an iterator pointing to
	// the first element in the range [first, last)
	// that is greater than value, or last if no such element is found
	// private static int upperBoundNew(long[] arr, long num){
	//
	// int start = 0;
	// int end = arr.length - 1;
	// int index = 0;
	// int len = arr.length;
	// int mid = 0;
	// while(true){
	// if(start > end){
	// break;
	// }
	// mid = (start + end) / 2;
	// if(arr[mid] > num){
	// end = mid - 1;
	// }
	// else if(arr[mid] < num){
	// start = mid + 1;
	// }
	// else{
	// while(mid < len && arr[mid] == num){
	// mid++;
	// }
	// if(mid == len - 1 && arr[mid] == num){
	// return mid + 1;
	// }
	// else{
	// return mid;
	// }
	// }
	// }
	// if(arr[mid] < num){
	// return mid + 1;
	// }
	// return mid;
	// }

	// private static int upperBound(long[] arr, long num) {
	//
	// int start = 0;
	// int end = arr.length;
	//
	// int mid = 0;
	// int index = 0;
	// while (true) {
	//
	//// System.out.println(start + " " + end);
	// if (start > end) {
	// break;
	// }
	// mid = (start + end) / 2;
	// if (arr[mid] > num) {
	// end = mid - 1;
	//
	// } else if (arr[mid] < num) {
	// start = mid + 1;
	// } else {
	// return mid;
	// }
	//
	//// System.out.println("a: " + start + " " + end);
	// }
	//
	// // System.out.println(mid);
	// if (arr[mid] < num) {
	// index = mid + 1;
	// } else {
	// index = mid;
	// }
	// return index;
	// }

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

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

		public String next() {
			try {
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					tokenizer = new StringTokenizer(reader.readLine());

				}
			} catch (IOException e) {
				return null;
			}
			return tokenizer.nextToken();
		}

		public String nextLine() {
			String line = null;
			try {
				tokenizer = null;
				line = reader.readLine();
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
			return line;
		}

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

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

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

		public boolean hasNext() {
			try {
				while (tokenizer == null || !tokenizer.hasMoreTokens()) {
					tokenizer = new StringTokenizer(reader.readLine());
				}
			} catch (Exception e) {
				return false;
			}
			return true;
		}
	}
}