Algorithms and Data Structures

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 of t
  • s is a suffix of t
  • s is a substring of t
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

To check your solution you need to sign in
Sign in to continue