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 PYTHON):

Solution:
from __future__ import print_function # for PyPy2
from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math
 
g   = lambda : stdin.readline().strip()
gl  = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1e9)+7
inf = float("inf")


def createPi(pat):
	n = len(pat)
	pi = [0]*n
	for i in range(1, n):
		j = pi[i-1]
		while j > 0 and pat[i]!=pat[j]:
			j = pi[j-1]
		pi[i] = j + (1 if s[i]==s[j] else 0)
	return pi


def find(pat, string):
	# print(pat, string)
	pi = createPi(pat)
	prev = 0
	i = 0
	while i < len(string):
		# print(prev, i)
		if string[i] == pat[prev]:
			prev += 1;i+=1
		elif prev:
			prev = pi[prev-1]
		else:
			i += 1
		if prev == len(pat): return True

	return False


s = g()
n = len(s)
rs = s[::-1]
string = s[1:-1]
pi = createPi(s)
arr = [];prev=pi[-1]
while prev:
	arr.append(prev)
	prev = pi[prev-1]
l, r = 0, len(arr)-1
# print(l, r)
# print(arr)
ans = 0
while l <= r:
	mid = (l+r)//2
	idx = arr[mid]
	# print(s[:idx][::-1], rs[:idx])
	if s[:idx][::-1] == rs[:idx] and find(s[:idx], string):
		r = mid - 1
		ans = idx
	else:
		l = mid + 1

print(s[:ans] if ans else  "Just a legend")