Search it Everywhere!
Given a very long text
t, the company is trying to find the longest substring
sthat satisfies several conditions:
sis a prefix of
sis a suffix of
sis a substring of
Can you help them do that?
The only line of the input contains the text
t(1 ≤ |t| ≤ ).
The program should print the longest possible string
sthat satisfies all the conditions, or
Impossibleif it’s not possible to find such a string.
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB