Kaladėlės

시간 제한1초메모리 제한1024 MB

요약

같은 문자가 이웃하지 않도록 문자를 다시 배열하고, 불가능하면 NE를 출력합니다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬, 해시맵, 구현
정답자: 아직 제출이 없습니다

문제

Linas gimtadienio proga gavo Lego konstruktorių, sudarytą iš $N$ įvairiaspalvių kaladėlių. Visas kaladėles Linas sudėliojo į eilę ir užrašė kiekvienos spalvą kaip didžiąją lotynišką raidę:

B D A A R A R B K A A

Bežaisdamas su kaladėlėmis, Linas jas perdėliojo taip, kad jokios tos pačios spalvos kaladėlės nebūtų viena šalia kitos:

A B R A K A D A B R A

Linui kilo klausimas: ar kito konstruktoriaus kaladėles taip pat pavyktų perdėlioti taip, kad tos pačios spalvos kaladėlės nebūtų greta?

Parašykite progamą, kuri nustatytų, ar įmanoma perdėlioti kaladėles norimu būdu, ir jei įmanoma, išvestų perdėliotų kaladėlių spalvų seką.

입력

Pirmoje eilutėje įrašytas kaladėlių kiekis $N$ .

Antroje eilutėje įrašyta $N$ tarpais atskirtų didžiųjų lotyniškų raidžių.

출력

Jeigu įmanoma seką perdėlioti taip, kad greta nebūtų vienspalvių kaladėlių, išveskite $N$ tarpais atskirtų raidžių, atitinkančių kaladėlių spalvas. Jeigu yra daugiau nei vienas teisingas atsakymas, išveskite bet kurį.

Jeigu neįmanoma – išveskite žodį NE.

제한

$1 ≤ N ≤ 1\\,000$

예제2

예제 1

입력

11
B D A A R A R B K A A

예상 출력

A B R A K A D A B R A

예제 2
입력
```
8
A C A B A A C A
```
예상 출력
```
NE
```