P6739 [BalticOI 2014] Three Friends (Day1)

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

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

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

#### 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](https://boi.cses.fi/files/boi2014_day1.pdf)。 Translated by ChatGPT 5