测试数据来自 wjszez/2092

【问题描述】
省省是一个爱玩游戏的信息竞赛的选手。
他正在和电脑玩一个好玩的游戏。他们写下一个有N个字母的序列。他们两都在尝试用序列中的字母来组成一个单词（即使这个单词并不存在）。他们轮流从序列中取出一个字母，并且把它放到他们自己单词的末尾。省省先取。当序列中没有剩余的字母时游戏结束。
如果一个单词的字典序比另一个单词的字典序小，我们说这个单词比另一个单词美丽。在游戏结束时，有更美的单词的选手获得胜利。如果他们有同样美丽的单词，那么他们都失败。
省省是一个有着比电脑更加厉害头脑的选手，因此他决定只取最右边的字母，这样子电脑才有可能胜利。知道了他的想法，电脑希望知道，他是否可能胜利，以及游戏结束时它能够得到的最美丽的单词。
【输入格式】
第一行包括一个数字N
第二行包括N个字母。表示最一开始的序列。所有的字母都是字母表中的小写字母。
【输出格式】
第一行输出DA或者NE。若是电脑可以取得胜利输出DA，反之输出NE。
第二行输出电脑在游戏结束时所能得到的最美丽的单词。
【输入输出样例】
Input
2
Ne
Output
NE
N
Input
4
Kava
Output
DA
ak
Input
8
Cokolada
Output
DA
acko
【数据范围】
对于50%的数据 N<=1000
对于100%的数据 N<=100000

【时间限制】 1000ms
【空间限制】 32M