Задача №114085. Три друга
Три друга любят играть в следующую игру. Первый друг выбирает строку \(S\). Затем второй друг создает новую строку \(T\), который состоит из двух копий строки \(S\). Наконец, третий друг вставляет одну букву в начале, в конце или где-то внутри строки \(T\), тем самым создавая новую строку \(U\).
Дана строка \(U\), ваша задача – восстановить исходную строку \(S\).
Первая строка ввода содержит \(N\) (\(2 \leq N \leq 2\,000\,001\)) – длину итоговой строки \(U\). Сама строка \(U\) задается на второй строке. Она состоит из \(N\) заглавных английских букв.
Ваша программа должна напечатать исходную строку \(S\). Однако есть два исключения:
-
Если конечная строка \(U\) не могла быть создана с помощью вышеуказанной процедуры, необходимо вывести
NOT POSSIBLE
.
- Если исходная строка \(S\) определяется неоднозначно, следует напечатать NOT UNIQUE .
Решения, правильно работающие на тестах, в которых \(2 \leq N \leq 2001\) будут оцениваться в \(35\) баллов.
7 ABXCABC
ABC
9 ABABABABA
NOT UNIQUE
6 ABCDEF
NOT POSSIBLE