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