14511451 SUSTech Online Judge
Problem 1451 --String Problem G

1451: String Problem G

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 81  Solved: 42
[Submit][Status][Web Board]

Description

Given you a String \(S\), you are required to find the longest string that shows in \(S\)'s prefix, suffix and also shows in \(S\)'s inner place. Here we define the inner place of a string is the substring without its first and last character. For example, the inner place of string \(abcde\) is \(bcd\).

Input

One line containing \(S \ (1\leq |S|\leq 10^6)\)

Output

If you can find such a string, print it, otherwise print "Just a legend" (without quote)

Sample Input

abababa

Sample Output

aba

HINT

Source

 

[Submit][Status]