Description

There is a string $S$, and we perform the following operations on it:

1. Copy $S$ into two copies and store them in the string $T$.
2. Insert one character at some position in $T$ to obtain the string $U$.

Now, given $U$, find $S$.

Input Format

The first line contains an integer $N$, representing the length of $U$.
The second line contains $N$ characters, representing the string $U$.

Output Format

• If it is impossible to derive $U$ from $S$ using the steps above, output NOT POSSIBLE.
• If the $S$ obtained from $U$ is not unique, output NOT UNIQUE.
• Otherwise, output the string $S$.

7
ABXCABC

ABC

6
ABCDEF

NOT POSSIBLE

9
ABABABABA

NOT UNIQUE

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (35 pts): $N \le 2001$.
• Subtask 2 (65 pts): no special constraints.

For $100\%$ of the testdata, $2 \le N \le 2 \times 10^6+1$, and $U$ is guaranteed to contain only uppercase letters.

Notes

Translated from BalticOI 2014 Day1 B Three Friends。

Translated by ChatGPT 5