本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1133. 【 哈希和哈希表】Three Friends


Description

Three friends like to play the following game. The first friend chooses a string S. Then the second friend constructs a new string T that consists of two copies of the string S. finally, the third friend inserts one letter at the beginning, the end or somewhere inside the string T, thereby creating a string U.
You are given the string U and your task is to reconstruct the original string S.

Input

The first line of the input contains N(2 ≤ N ≤ 2000001), the length of the final string U. The string U itself is given on the second line. It consists of N uppercase English letters (A, B, C, . . . , Z).

Output

Your program should print the original string S. However, there are two exceptions:
1.If the final string U could not have been created using the above procedure, you should print NOT POSSIBLE.
2.If the original string S is not unique, you should print NOT UNIQUE.

Samples

Input Copy
7
ABXCABC
Output
ABC

Source

信息学奥赛一本通·提高篇
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
My history solutions

You didn't submit any solution!
Submit your solution

Login Register