#1803 단어게임

18  1 s   128 MB  

Description

승규와 승주가 영어 단어를 가지고 게임을 하고자 한다.
게임의 규칙은 다음과 같다.

게임을 하다 보니 승규가 매번 이기게 되어서 시시해진 나머지 승규는 선택하는 문자를 맨 오른쪽에 위치한 문자를 선택한다고 하자. 그럴 때 매번 지던 승주가 이길 수 있는 방법은 존재하는지 찾아내는 프로그램을 작성하라.

Input

입력의 첫 줄에는 단어의 길이 N ( 2≤N≤100,000 )이 입력된다. N은 짝수다.

그 다음 줄에는 N개의 영문 소문자로 이뤄진 게임에 사용할 단어가 입력된다.

Output

승주가 이길 수 있을 경우 "DA"를 출력하고, 그렇지 못할 경우 "NE"를 출력한다.
그 다음 줄에는 승주가 만들 수 있는 사전 순으로 가장 빠른 단어를 출력한다.

Sample Input

Sample Output

2
ne
NE
n

Sample Input 2

4
kava

Sample Output 2

DA
ak

Sample Input 3

8
cokolada

Sample Output 3

DA
acko