Problem Description

There is a string \( S \), and we perform the following operations on it:

1. Duplicate \( S \) to form a string \( T \).
2. Insert a single character at some position in \( T \) to obtain string \( U \).

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 not possible to derive \( U \) from \( S \) through the above steps, output NOT POSSIBLE.
• If the \( S \) derived from \( U \) is not unique, output NOT UNIQUE.
• Otherwise, output the string \( S \).

Sample Input and Output

Sample Input #1

7
ABXCABC

Sample Output #1

ABC

Sample Input #2

6
ABCDEF

Sample Output #2

NOT POSSIBLE

Sample Input #3

9
ABABABABA

Sample Output #3

NOT UNIQUE

Notes

Data Size and Constraints

This problem uses batched testing.

• Subtask 1 (35 points): \( N \le 2001 \).
• Subtask 2 (65 points): No additional constraints.

For \( 100\% \) of the data, \( 2 \le N \le 2 \times 10^6 + 1 \), and \( U \) consists only of uppercase letters.

Notes

Translated from BalticOI 2014 Day1 B Three Friends.

见题面 Input 部分

见题面 Output 部分