시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 140 37 32 32.000%

문제

준규, 해빈, 진욱이는 다음과 같은 게임을 한다.

먼저, 준규가 문자열 S를 고른다. 그 다음, 해빈이는 S의 뒤에 S를 붙인 새로운 문자열 T를 만든다. 마지막으로 진욱이는 문자열 T의 어딘가(시작이나 끝도 가능)에 문자 하나를 삽입해 문자열 U를 만든다.

U가 주어졌을 때, S를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 U의 길이 N이 주어지고, 둘째 줄에 U가 주어진다. U는 알파벳 대문자로만 이루어져 있다. (2 ≤ N ≤ 2000001)

출력

  1. U를 만들 수 없는 경우에는 "NOT POSSIBLE"을 출력한다.
  2. U를 만들 수 있는 문자열 S가 유일하지 않다면, "NOT UNIQUE"를 출력한다.
  3. 나머지 경우에는 S를 출력한다.

예제 입력 1

7
ABXCABC

예제 출력 1

ABC

힌트

W3sicHJvYmxlbV9pZCI6IjEwMDk2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMTM4IFx1Y2U1Y1x1YWQ2YyIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90aHJlZWZyaWVuZC5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTA2cHg7IHdpZHRoOjE3N3B4XCIgXC8+XHVjOTAwXHVhZGRjLCBcdWQ1NzRcdWJlNDgsIFx1YzljNFx1YzZiMVx1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCwgXHVjOTAwXHVhZGRjXHVhYzAwIFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHViOTdjIFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHVkNTc0XHViZTQ4XHVjNzc0XHViMjk0IFNcdWM3NTggXHViNGE0XHVjNWQwIFNcdWI5N2MgXHViZDk5XHVjNzc4IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWJiMzhcdWM3OTBcdWM1ZjQgVFx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YyBcdWM5YzRcdWM2YjFcdWM3NzRcdWIyOTQgXHViYjM4XHVjNzkwXHVjNWY0IFRcdWM3NTggXHVjNWI0XHViNTE4XHVhYzAwKFx1YzJkY1x1Yzc5MVx1Yzc3NFx1YjA5OCBcdWIwNWRcdWIzYzQgXHVhYzAwXHViMmE1KVx1YzVkMCBcdWJiMzhcdWM3OTAgXHVkNTU4XHViMDk4XHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU3NCBcdWJiMzhcdWM3OTBcdWM1ZjQgVVx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlVcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgU1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgVVx1Yzc1OCBcdWFlMzhcdWM3NzQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDAgVVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFVcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjMwMFx1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAyMDAwMDAxKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxvbD5cclxuXHQ8bGk+VVx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7Tk9UIFBPU1NJQkxFJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+VVx1Yjk3YyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YWMwMCBcdWM3MjBcdWM3N2NcdWQ1NThcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0LCAmcXVvdDtOT1QgVU5JUVVFJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHViMDk4XHViYTM4XHVjOWMwIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBTXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMDk2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhyZWUgRnJpZW5kcyIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC90aHJlZWZyaWVuZC5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6MTA2cHg7IHdpZHRoOjE3N3B4XCIgXC8+VGhyZWUgZnJpZW5kcyBsaWtlIHRvIHBsYXkgdGhlIGZvbGxvd2luZyBnYW1lLiBUaGUgZmlyc3QgZnJpZW5kIGNob29zZXMgYSBzdHJpbmcgUy4gVGhlbiB0aGUgc2Vjb25kIGZyaWVuZCBjb25zdHJ1Y3RzIGEgbmV3IHN0cmluZyBUIHRoYXQgY29uc2lzdHMgb2YgdHdvIGNvcGllcyBvZiB0aGUgc3RyaW5nIFMuIEZpbmFsbHksIHRoZSB0aGlyZCBmcmllbmQgaW5zZXJ0cyBvbmUgbGV0dGVyIGF0IHRoZSBiZWdpbm5pbmcsIHRoZSBlbmQgb3Igc29tZXdoZXJlIGluc2lkZSB0aGUgc3RyaW5nIFQsIHRoZXJlYnkgY3JlYXRpbmcgYSBzdHJpbmcgVS48XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiB0aGUgc3RyaW5nIFUgYW5kIHlvdXIgdGFzayBpcyB0byByZWNvbnN0cnVjdCB0aGUgb3JpZ2luYWwgc3RyaW5nIFMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgTiwgdGhlIGxlbmd0aCBvZiB0aGUgZmluYWwgc3RyaW5nIFUuIFRoZSBzdHJpbmcgVSBpdHNlbGYgaXMgZ2l2ZW4gb24gdGhlIHNlY29uZCBsaW5lLiBJdCBjb25zaXN0cyBvZiBOIHVwcGVyY2FzZSBFbmdsaXNoIGxldHRlcnMgKEEsIEIsIEMsIC4uLiAsIFopLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBzaG91bGQgcHJpbnQgdGhlIG9yaWdpbmFsIHN0cmluZyBTLiBIb3dldmVyLCB0aGVyZSBhcmUgdHdvIGV4Y2VwdGlvbnM6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+SWYgdGhlIGZpbmFsIHN0cmluZyBVIGNvdWxkIG5vdCBoYXZlIGJlZW4gY3JlYXRlZCB1c2luZyB0aGUgYWJvdmUgcHJvY2VkdXJlLCB5b3Ugc2hvdWxkIHByaW50IE5PVCBQT1NTSUJMRS48XC9saT5cclxuXHQ8bGk+SWYgdGhlIG9yaWdpbmFsIHN0cmluZyBTIGlzIG5vdCB1bmlxdWUsIHlvdSBzaG91bGQgcHJpbnQgTk9UIFVOSVFVRS48XC9saT5cclxuPFwvb2w+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2014 2번