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

public class Main {
	static final int M = 1000000007;

	static class FastScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}

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

		long[] readArrayLong(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		int[] readArrayInt(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble() {return Double.parseDouble(next());}
	}

	// sorting template
	static void sortLong(long[] a) {
		ArrayList<Long> l = new ArrayList<>();
		for (long i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static void sortInt(int[] a) {
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < a.length; i++)
			a[i] = l.get(i);
	}

	static class Graph {
		private ArrayList<Integer> adj[];
		public String s;
		public String dpch;

		Graph(int n) {
			adj = new ArrayList[n + 1];
			for (int i = 1; i <= n; i++) {
				adj[i] = new ArrayList<>();
			}
		}

		void addEdges(int u, int v) {
			adj[u].add(v);
			adj[v].add(u);
		}

		void dfs(int node, int par, boolean[] vis, int timer) {
			vis[node] = true;
			in[node] = timer++;
			for(int u: adj[node]){
				if(u==par) continue;
				if(vis[u]){
					if(in[node]>in[u])
					System.out.println(node+" "+u);
				}else {
					dfs(u, node, vis, timer);
					System.out.println(node + " " + u);
				}
			}
		}
		int bfs(int v, int e, boolean[] vis) {
			int sum = 1;
			Queue<Integer> q = new LinkedList<>();
			q.add(v);
			vis[v] = true;
			while (q.size() > 0) {
				int n = q.size();
				for(int i=0;i<n;i++){
					int node = q.poll();
					for (int u : adj[node]) {
						if (!vis[u]) {
							if(u==e){
								return sum;
							}
							vis[u] = true;
							q.add(u);
						}
					}
				}
				sum++;
			}
			return sum;
		}

		public void dfs(boolean[] vis, int node, int par) {
			vis[node] = true;
			in[node] = low[node] = timer++;
			for(int u: adj[node]){
				if(u==par) continue;;
				if(vis[u]){
					low[node] = Math.min(low[node], in[u]);
					if(in[node]>in[u]){
						ans.add(new Pair<>(node, u));
					}
				}else {
					dfs(vis, u, node);
					if(low[u]>in[node]) {
						bridges++;
						if(bridges>0)return;
					}
					ans.add(new Pair<>(node, u));
					low[node] = Math.min(low[node], low[u]);
				}
			}
		}
	}

	static class Pair<F, S> {
		F first;
		S second;

		Pair(F first, S second) {
			this.first = first;
			this.second = second;
		}

		public F getFirst() {
			return this.first;
		}

		public S getSecond() {
			return this.second;
		}
		// Sort on basis of first term, reverse p1.first and p2.first to sort in desc
		// Collections.sort(a, (p1, p2) -> (p1.first - p2.first));

		// Sort on the basis of second term, reverse p1.second and p2.second to sort
		// in
		// desc
		// Collections.sort(a, (p1, p2) -> (p1.second - p2.second));
	}

	static long __gcd(long a, long b) {
		if (b == 0)
			return a;
		return __gcd(b, a % b);
	}

	public static int timer, bridges;
	public static int[] in, low;
	static ArrayList<Pair<Integer, Integer>> ans;
	private static HashMap<Integer, Integer> getHash(int[] a){
		HashMap<Integer, Integer> hm = new HashMap<>();
		for(int i: a){
			hm.put(i, hm.getOrDefault(i,0)+1);
		}
		return hm;
	}

	public static void main(String[] args) throws IOException {
		FastScanner fs = new FastScanner();
//		int t = fs.nextInt();
		int t = 1;
		StringBuffer res = new StringBuffer();
		for (int tt = 1; tt <= t; tt++) {
			String s = fs.next();
			int[] z = zFunction(s);
			int mx[] = new int[s.length()]; //max
			mx[0] = 0;
			for(int i=1; i<s.length(); i++){
				mx[i] = Math.max(mx[i-1],z[i]);
			}
			int ans = -1;
			for(int i=s.length()-1; i>0; i--){
				if(i+z[i] == s.length() && mx[i-1] >= z[i]){
					ans = i;
				}
			}
			if (ans == -1)
				res.append("Just a legend");
			else {
				for(int j=ans; j<ans + z[ans]; j++)
					res.append(s.charAt(j));
			}
		}
		System.out.println(res);
	}

	private static boolean search(int[] a, int k) {
		int left = 0;
		int right = a.length-1;
		while (left < right) {
			int mid = left + (right - left) / 2;
			if (a[mid]==k) {
				return true;
			} else if(a[mid]>k){
				right = mid-1;
			}else left = mid;
		}
		return false;
	}

	private static int[] zFunction(String input) {
		int n = input.length();
		int[] z = new int[n];
		int left = 0, right = 0;
		for(int i=1;i<n;i++){
			if(i>right){
				left = right = i;
				while (right<n&&input.charAt(right)==input.charAt(right-left)){
					right++;
				}
				z[i] = right - left;
				right--;
			}else{
				int k = i - left;
				if(z[k]<right-i+1){
					z[i] = z[k];
				}else{
					left = i;
					while (right<n && input.charAt(right)==input.charAt(right-left)){
						right++;
					}
					z[i] = right - left;
					right--;
				}
			}
		}
		return z;
	}
}