#P1661. Friends

Friends

Description

本题译自 BalticOI 2014 Day1 T2「Three Friends

给定一个字符串 S,先将字符串 S 复制一次(变成双倍快乐),得到字符串 T,然后在 T 中插入一个字符,得到字符串 U。

给出字符串 U,重新构造出字符串 S。

所有字符串只包含大写英文字母。

Input Format

第一行一个整数 N,表示字符串 U 的长度。 第二行一个长度为 N 的字符串,表示字符串 U。

Output Format

一行一个字符串,表示字符串 S。 特别地: 如果字符串无法按照上述方法构造出来,输出 NOT POSSIBLE; 如果字符串 S 不唯一,输出 NOT UNIQUE。
7
ABXCABC
ABC

Hint

Source

Hash KMP