题目描述

解决了繁琐的任务后，Mirko 决定与他的好朋友 Slavko 一起玩游戏。

他们在一张纸上写了一个含有 $n$ 个字母的序列。每个人轮流使用序列中的字母拼写一个单词，即从序列中删除单个字母并将其附加到单词的末尾。Mirko 开始了第一回合。当序列中没有剩余字母时，游戏结束。

一个比另一个单词更美丽的单词指这个单词按照字典序排在另一个单词前面。在游戏结束时拥有更美丽单词的玩家将获胜。 如果两个玩家的单词都一样，他们就都输了这一轮。

Mirko 玩得比 Slavko 更好，因此他决定通过始终选择序列中最右边的字母来使 Slavko 玩得更容易一些。 知道了这一点，Slavko 想知道他是否有可能获胜，以及他可能得到的最美丽的单词是什么。

输入格式

第一行一个整数 $n$，具体含义请见题目描述。

第二行一个长度为 $n$ 的字符串，表示初始序列。

输出格式

第一行一个大写字符串 NE 或 DA，DA 表示 Slavko 可能获胜，NE 表示 Slavko 不可能获胜。

第二行一个字符串，表示 Slavko 可能得到的最美丽的单词。

2
ne

NE
n

4
kava

DA
ak

8
cokolada

DA
acko

提示

数据规模与约定

• 对于 $50\%$ 的数据，保证 $n = 2\times k(1 \leq k \leq 500)$ 且 $k$ 为整数。
• 对于 $100\%$ 的数据，保证 $n = 2\times k(1 \leq k \leq 10^5)$ 且 $k$ 为整数，所有读入的、输出的第二行的字符均为小写字母。

说明

• 本题满分 $80$ 分。
• 题目译自 COCI2010-2011 CONTEST #2 IGRA，译者
  https://www.luogu.com.cn/user/115711