在解决了繁琐的作业后，Mirko 决定和他的好朋友 Slavko 玩一个游戏。

他们在纸上写下了一个由 $N$ 个字母组成的序列。他们每个人都试图用序列中的字母拼出一个单词。他们轮流进行操作，每次操作包括从序列中移除一个字母并将其追加到自己单词的末尾。Mirko 先手。当序列中没有剩余字母时，游戏结束。

我们定义，如果一个单词在字典序上更靠前，则它比另一个单词更“美”。在游戏结束时，拥有更美的单词的玩家获胜。如果两人的单词相同，则两人都输。

Mirko 的水平比 Slavko 高得多，因此他决定让着 Slavko：在轮到他时，他总是选择当前序列中最右侧的剩余字母。得知这一点后，Slavko 想知道自己是否有获胜的可能，以及他在游戏结束时能获得的最美的单词是什么。

输入格式

输入的第一行包含一个正偶数 $N$ ($2 \le N \le 100\,000$)。

输入的第二行包含 $N$ 个字符，即初始字母序列。所有字符均为英文小写字母。

输出格式

输出的第一行，如果 Slavko 有可能获胜，则输出 DA，否则输出 NE。

输出的第二行必须包含 Slavko 在游戏结束时能获得的最美的单词。

子任务

对于 $50\%$ 的测试数据，数量 $N$ 不超过 $1000$。

样例

输入样例 1

2
ne

输出样例 1

NE
n

输入样例 2

4
kava

输出样例 2

DA
ak

输入样例 3

8
cokolada

输出样例 3

DA
acko