시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 124 46 42 44.681%

문제

상근이는 희원이와 놀기 위해 집에서 게임을 준비해 왔다. 먼저, 한 종이에 한 글자씩 쓰여 있고, 이러한 종이가 N개가 한 줄로 놓여져 있다. 그리고, 이 종이를 모두 하나로 모아서 단어를 만든다. 그 다음에 턴을 번갈아가면서 단어에서 종이 한 장을 가져가고 자기 단어의 뒤쪽에 붙인다. 상근이가 게임을 먼저하고, 더 이상 가져갈 종이가 없으면 게임을 종료한다.

두 단어 A와 B가 있을때, A가 B보다 사전순으로 앞선다면, A는 B보다 아름답다. 두 플레이어가 각자 만든 단어 중에서 더 아름다운 단어를 만든 사람이 게임을 이긴다. 만약, 두 사람이 같은 단어를 만들었다면, 둘 다 지는 경우다.

상근이는 이 게임을 엄청나게 잘하지만, 희원이는 아직 규칙도 헷갈리는 상황이다. 따라서, 상근이는 희원이를 위해 조금 다른게 게임을 하려고 한다. 상근이는 항상 단어의 가장 오른쪽에 있는 종이를 집어간다.

위와 같이 상근이가 항상 오른쪽에 있는 종이만 집어갈 때, 희원이가 상근이를 이길 수 있는지 구하고, 만들 수 있는 가장 아름다운 단어를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 짝수 N이 주어진다. (2 ≤ N ≤ 100 000)

둘재 줄에 종이에 적혀져있는 글자가 순서대로 주어진다. 글자는 모두 알파벳 소문자로만 이루어져 있다.

출력

만약, 희원이가 이길 수 있다면 첫째 줄에 "DA"를, 없다면 "NE"를 출력한다. 둘째 줄에는 희원이가 만들 수 있는 가장 아름다운 단어를 출력한다.

예제 입력 1

8
cokolada

예제 출력 1

DA
acko
W3sicHJvYmxlbV9pZCI6IjI4NzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViMmU4XHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVkNzZjXHVjNmQwXHVjNzc0XHVjNjQwIFx1YjE4MFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjOWQxXHVjNWQwXHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM5MDBcdWJlNDRcdWQ1NzQgXHVjNjU0XHViMmU0LiBcdWJhM2NcdWM4MDAsIFx1ZDU1YyBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVkNTVjIFx1YWUwMFx1Yzc5MFx1YzUyOSBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHVhY2UwLCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjODg1XHVjNzc0XHVhYzAwIE5cdWFjMWNcdWFjMDAgXHVkNTVjIFx1YzkwNFx1Yjg1YyBcdWIxOTNcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFkZjhcdWI5YWNcdWFjZTAsIFx1Yzc3NCBcdWM4ODVcdWM3NzRcdWI5N2MgXHViYWE4XHViNDUwIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWJhYThcdWM1NDRcdWMxMWMgXHViMmU4XHVjNWI0XHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWQxMzRcdWM3NDQgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1YjJlOFx1YzViNFx1YzVkMFx1YzExYyBcdWM4ODVcdWM3NzQgXHVkNTVjIFx1YzdhNVx1Yzc0NCBcdWFjMDBcdWM4MzhcdWFjMDBcdWFjZTAgXHVjNzkwXHVhZTMwIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWI0YTRcdWNhYmRcdWM1ZDAgXHViZDk5XHVjNzc4XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YmEzY1x1YzgwMFx1ZDU1OFx1YWNlMCwgXHViMzU0IFx1Yzc3NFx1YzBjMSBcdWFjMDBcdWM4MzhcdWFjMDggXHVjODg1XHVjNzc0XHVhYzAwIFx1YzVjNlx1YzczY1x1YmE3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjODg1XHViOGNjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViMmU4XHVjNWI0IEFcdWM2NDAgQlx1YWMwMCBcdWM3ODhcdWM3NDRcdWI1NGMsIEFcdWFjMDAgQlx1YmNmNFx1YjJlNCBcdWMwYWNcdWM4MDRcdWMyMWNcdWM3M2NcdWI4NWMgXHVjNTVlXHVjMTIwXHViMmU0XHViYTc0LCBBXHViMjk0IEJcdWJjZjRcdWIyZTQgXHVjNTQ0XHViOTg0XHViMmY1XHViMmU0LiBcdWI0NTAgXHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YWMwMVx1Yzc5MCBcdWI5Y2NcdWI0ZTAgXHViMmU4XHVjNWI0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWIzNTQgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWI5Y2NcdWI0ZTAgXHVjMGFjXHViNzhjXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM3NzRcdWFlMzRcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjMTlcdWM3NDAgXHViMmU4XHVjNWI0XHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNFx1YmE3NCwgXHViNDU4IFx1YjJlNCBcdWM5YzBcdWIyOTQgXHVhY2JkXHVjNmIwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWM1YzRcdWNjYWRcdWIwOThcdWFjOGMgXHVjNzk4XHVkNTU4XHVjOWMwXHViOWNjLCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWIyOTQgXHVjNTQ0XHVjOWMxIFx1YWRkY1x1Y2U1OVx1YjNjNCBcdWQ1ZjdcdWFjMDhcdWI5YWNcdWIyOTQgXHVjMGMxXHVkNjY5XHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ3NmNcdWM2ZDBcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0IFx1Yzg3MFx1YWUwOCBcdWIyZTRcdWI5NzhcdWFjOGMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHViMmU4XHVjNWI0XHVjNzU4IFx1YWMwMFx1YzdhNSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWM5ZDFcdWM1YjRcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1ZDU2ZFx1YzBjMSBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Yzg4NVx1Yzc3NFx1YjljYyBcdWM5ZDFcdWM1YjRcdWFjMDggXHViNTRjLCZuYnNwO1x1ZDc2Y1x1YzZkMFx1Yzc3NFx1YWMwMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWI5N2MgXHVjNzc0XHVhZTM4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHVhY2UwLCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViOTg0XHViMmU0XHVjNmI0IFx1YjJlOFx1YzViNFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWRkXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAgMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM3YWMgXHVjOTA0XHVjNWQwIFx1Yzg4NVx1Yzc3NFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM4MzhcdWM3ODhcdWIyOTQgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWUwMFx1Yzc5MFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YjljY1x1YzU3ZCwgXHVkNzZjXHVjNmQwXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzOCBcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgJnF1b3Q7REEmcXVvdDtcdWI5N2MsIFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDtORSZxdW90O1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNzZjXHVjNmQwXHVjNzc0XHVhYzAwIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM1NDRcdWI5ODRcdWIyZTRcdWM2YjQgXHViMmU4XHVjNWI0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODcxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSUdSQSIsImRlc2NyaXB0aW9uIjoiPHA+SGF2aW5nIHNvbHZlZCB0aGUgdGVkaW91cyBhc3NpZ25tZW50LCBNaXJrbyBkZWNpZGVkIHRvIHBsYXkgYSBnYW1lIHdpdGggaGlzIGdvb2QgZnJpZW5kIFNsYXZrby4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhleSBoYXZlIHdyaXR0ZW4gYSBzZXF1ZW5jZSBvZiBOIGxldHRlcnMgb24gYSBwaWVjZSBvZiBwYXBlci4gRWFjaCBvbmUgb2YgdGhlbSBpcyB0cnlpbmcgdG8gcHV0IHRvZ2V0aGVyIGEgd29yZCB1c2luZyBsZXR0ZXJzIGZyb20gdGhlIHNlcXVlbmNlLiBUaGV5IGFsdGVybmF0ZSB0YWtpbmcgdHVybnMgY29uc2lzdGluZyBvZiByZW1vdmluZyBhIHNpbmdsZSBsZXR0ZXIgZnJvbSB0aGUgc2VxdWVuY2UgYW5kIGFwcGVuZGluZyBpdCB0byB0aGUgZW5kIG9mIHRoZWlyIHdvcmQuIE1pcmtvIGhhcyB0aGUgZmlyc3QgdHVybi4gVGhlIGdhbWUgZW5kcyB3aGVuIG5vIGxldHRlcnMgYXJlIHJlbWFpbmluZyBpbiB0aGUgc2VxdWVuY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldlIGRlZmluZSBhIHdvcmQgdG8gYmUgbW9yZSBiZWF1dGlmdWwgdGhhbiBhbm90aGVyIHdvcmQgaWYgaXQgY29tZXMgZmlyc3QgYWxwaGFiZXRpY2FsbHkuIFRoZSBwbGF5ZXIgd2hvIGhhcyB0aGUgbW9yZSBiZWF1dGlmdWwgd29yZCBhdCB0aGUgZW5kIG9mIHRoZSBnYW1lIHdpbnMuIElmIGJvdGggcGxheWVycyBoYXZlIGVxdWFsIHdvcmRzLCB0aGV5IGJvdGggbG9zZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gaXMgYSBtdWNoIGJldHRlciBwbGF5ZXIgdGhhbiBTbGF2a28sIHNvIGhlIGhhcyBkZWNpZGVkIHRvIG1ha2UgaXQgZWFzaWVyIGZvciBTbGF2a28gYnkgYWx3YXlzIHNlbGVjdGluZyB0aGUgcmlnaHRtb3N0IHJlbWFpbmluZyBsZXR0ZXIgaW4gdGhlIHNlcXVlbmNlLiBLbm93aW5nIHRoaXMsIFNsYXZrbyB3YW50cyB0byBmaW5kIG91dCBpZiBpdCBpcyBwb3NzaWJsZSBmb3IgaGltIHRvIHdpbiBhbmQgd2hpY2ggaXMgdGhlIG1vc3QgYmVhdXRpZnVsIHdvcmQgaGUgY2FuIGVuZCB0aGUgZ2FtZSB3aXRoLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gZXZlbiBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDIgJmxlOyBOICZsZTsgMTAwIDAwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBvZiBpbnB1dCBjb250YWlucyBOIGNoYXJhY3RlcnMsIHRoZSBzdGFydGluZyBsZXR0ZXIgc2VxdWVuY2UuIEFsbCBjaGFyYWN0ZXJzIGFyZSBsb3dlciBjYXNlIGxldHRlcnMgZnJvbSB0aGUgRW5nbGlzaCBhbHBoYWJldC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluICZsZHF1bztEQSZyZHF1bzsgaWYgaXQgaXMgcG9zc2libGUgZm9yIFNsYXZrbyB0byB3aW4sIGFuZCAmbGRxdW87TkUmcmRxdW87IG90aGVyd2lzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG1vc3QgYmVhdXRpZnVsIHdvcmQgdGhhdCBTbGF2a28gY2FuIGhhdmUgYXQgdGhlIGVuZCBvZiB0aGUgZ2FtZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #2 3번