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 2000001$

Subtask 1 [35%]

$2\le |U|\le 2001$

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