미르코와 슬라브코는 함께 게임을 하기로 했다. 주어진 글자들을 이용하여 단어를 만드는 게임으로, 게임 방식은 아래와 같다.

• N 개의 글자를 종이 위에 쓴다.
• 차례는 미르코부터 시작하여 번갈아가며 진행된다.
• 자신의 차례가 되면 종이 위의 글자들 중 하나를 뽑아 자신의 단어 뒤에 붙이고, 뽑은 글자는 종이 위에서 지운다.
• 종이 위에 있는 글자가 모두 지워지면 게임이 끝난다.

미르코는 슬라브코보다 게임을 잘하기 때문에, 봐 주는 차원에서 항상 종이 위의 글자들 중 가장 오른쪽의 글자를 뽑기로 했다. 이 때 슬라브코는 (1) 자신이 이길 수 있는지, (2) 자신이 만들 수 있는 '가장 아름다운 단어'가 무엇인지 알고 싶어졌다.

입력

• 첫 번째 줄에 '짝수' 자연수 N 이 주어진다. (2 <= N <= 100,000)
• 다음 줄에 게임이 시작할 때 종이 위에 쓰는 N 글자의 '알파벳 소문자'로 이루어진 문자열이 주어진다.

출력

• 첫 번째 줄에 슬라브코가 이길 수 있다면 "DA"를, 아니면 "NE"를 출력한다.
• 두 번째 줄에 게임이 끝나고 슬라브코가 만들 수 있는 '가장 아름다운 단어'를 출력한다.

입출력 예

입력

2
ne

출력

NE
n

입력

4
kava

출력

DA
ak

입력

8
cokolada

출력

DA
acko

출처:coci 2010
번역:xdoju