Baltic Olympiad in Informatics: 2014 Day 1, Problem 2

Three friends like to play the following game. The first friend chooses a string ~S~. Then the second friend constructs a new string ~T~ that consists of two copies of the string ~S~. Finally, the third friend inserts one letter at the beginning, the end or somewhere inside the string ~T~, thereby creating a string ~U~.

Given the string ~U~, your task is to reconstruct the original string ~S~.

Constraints

~2 \le |U| \le 2\,000\,001~

Subtask 1 [35%]

~2 \le |U| \le 2\,001~

Subtask 2 [65%]

No additional constraints.

Input Specification

The only line of input contains the string ~U~, which consists of uppercase English letters.

Output Specification

Your program should print the original string ~S~. However, there are two exceptions:

1. If the final string ~U~ could not have been created using the above procedure, you should print NOT POSSIBLE.
2. If the original string ~S~ is not unique, you should print NOT UNIQUE.

Sample Input 1

ABXCABC

Sample Output 1

ABC

Sample Input 2

ABCDEF

Sample Output 2

NOT POSSIBLE

Sample Input 3

ABABABABA

Sample Output 3

NOT UNIQUE