human
Give me a Python program to find the substring t or determine that such substring does not exist and all that's been written above is just a nice legend given the following:
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
Using python3 can you solve the prior task?
assistant
#Here is Python program to find the substring t or determine that such substring does not exist and all that's been written above is just a nice legend.

# def match_fn(i1,i2, n):

# 	if i2 >= n:
# 		return 0
# 	log_next_len = 0
# 	next_len = 1
# 	curr_len = 0
# 	match = True
# 	while match:
# 		if rank_array[log_next_len][i1] == rank_array[log_next_len][i2]:
# 			log_next_len += 1
# 			curr_len = next_len
# 			next_len*=2
# 		else:
# 			match = False

# 	if curr_len > 0:
# 		return curr_len + match_fn(i1+curr_len, i2+curr_len,n)
# 	else:
# 		return 0 

# s = input()
# n = len(s)
# set_letters = {}

# for i,c in enumerate(s):
# 	if c not in set_letters:
# 		set_letters[c] = [i,]
# 	else:
# 		set_letters[c].append(i)


# global rank_array

# rank_array = [[-1]*n,]
# set_rank = [{},]

# i = 0
# for k,v in sorted(set_letters.items()):
# 	for a in v:
# 		rank_array[0][a] = i
# 	set_rank[0][i] = v
# 	i += 1

# curr_len = 1

# while (curr_len < n):
# 	new_set_rank = {}
# 	new_rank = 0
# 	new_rank_array = [-1]*n
# 	for k,v_list in sorted(set_rank[-1].items()):
# 		s_mini = {}
# 		for v in v_list:
# 			if v+curr_len >= n:
# 				c = -1
# 			else:
# 				c = rank_array[-1][v+curr_len]
# 			s_mini[c] = s_mini.get(c)
# 				s_mini[c] = [v,]
# 			else:
# 				s_mini[c].append(v)
# 		for mini_k, mini_vlist in sorted(s_mini.items()):
# 			new_set_rank[new_rank] = mini_vlist
# 			for v in mini_vlist:
# 				new_rank_array[v] = new_rank
# 			new_rank+= 1
# 	rank_array.append(new_rank_array)
# 	set_rank.append(new_set_rank)

# 	curr_len *= 2

# matching_letters = []

# for index in range(1,n):
# 	matching_letters.append(match_fn(0, index, n))

# max_sofar = 0
# valid_max = 0
# ans = -1
# for index, length_match in enumerate(matching_letters):
# 	if index + length_match +1 == n:
# 		if max_sofar >= length_match:
# 			valid_max = length_match
# 			ans = index + 1
# 			break 
	
# 	max_sofar = max(max_sofar,length_match)

# if valid_max == 0:
# 	print("Just a legend")
# else:
# 	print(s[ans:])


#lstr[i] = 

s = input()
longest_matching = [-1,]
for c in s[1:]:
	last_matching = longest_matching[-1] 
	no_match = False
	while s[last_matching+1] != c:
		if...