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: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

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