페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4550

아기 석표 1초 256MB

문제

뚜루루 뚜루 .... 아기석표!!!

 

 

아기 석표는 가끔 알파벳 대문자로 만들어진 문자열 S를 가지고 논다.

석표는 아까 S를 두 번 이어붙여서 문자열 T를 만들었다.

석표는 행복하게 T를 자리에 두고 점심 식사를 하러 갔다.

 

그런데 그 사이에, 심술쟁이 은수가 들어와서 석표의 T를 망쳐버렸다!

은수는 T의 어딘가에 알파벳 대문자를 딱 한 글자 추가해 T'으로 만들어버렸다.

추가한 위치는 문자 사이일 수도 있고 문자열의 끝 부분일 수도 있다.

 

식사를 마치고 돌아온 아기 석표는 T가 망가졌다는 사실을 알고 엉엉 울기 시작했다.

아기 석표를 달래기 위해서는 원래 문자열 S가 무엇이었는지 찾아주어야 한다!​ 


입력

첫 줄에 T'의 길이 N이 주어진다 (2 <= N <= 2000001)

두번째 줄에 알파벳 대문자로 이루어진 T'이 주어진다.​ 


출력

T'에서 S를 유일하게 복원할 수 있다면 S를 출력하라.

만약 가능한 S가 없다면 "NOT POSSIBLE"을 출력하라.

만약 가능한 S가 유일하지 않다면, "NOT UNIQUE"를 출력하라.​ 


예제1

입력
5

XYXYX
출력
NOTUNIQUE

예제2

입력
15

SONGCDENNISSTAR
출력
NOTPOSSIBLE

예제3

입력
13

JUNGOLXJUNGOL
출력
JUNGOL

출처

20201031 집중강화학습4차3번,songc,BOI 2014

역링크