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: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB