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