Description

After finishing a tedious task, Mirko decided to play a game with his good friend Slavko.

They write a sequence of $n$ letters on a sheet of paper. Each player takes turns using the letters in the sequence to spell a word: on each turn, they remove one letter from the sequence and append it to the end of their word. Mirko takes the first turn. The game ends when there are no letters left in the sequence.

One word is considered more beautiful than another if it comes earlier in lexicographical order. At the end of the game, the player with the more beautiful word wins. If both players' words are the same, then both of them lose that round.

Mirko plays better than Slavko, so he decided to make it easier for Slavko by always choosing the rightmost letter in the sequence. Knowing this, Slavko wants to know whether it is possible for him to win, and what the most beautiful word he can obtain is.

Input Format

The first line contains an integer $n$, whose meaning is described above.

The second line contains a string of length $n$, representing the initial sequence.

Output Format

The first line contains an uppercase string NE or DA. DA means Slavko can possibly win, and NE means Slavko cannot win.

The second line contains a string, the most beautiful word Slavko can possibly obtain.

2
ne

NE
n

4
kava

DA
ak

8
cokolada

DA
acko

Hint

Constraints

• For $50\%$ of the testdata, $n = 2\times k(1 \leq k \leq 500)$ and $k$ is an integer.
• For $100\%$ of the testdata, $n = 2\times k(1 \leq k \leq 10^5)$ and $k$ is an integer. All characters in the input and in the second output line are lowercase letters.

Notes

• The full score for this problem is $80$ points.
• Translated from COCI2010-2011 CONTEST #2 IGRA. Translator:
  https://www.luogu.com.cn/user/115711

Translated by ChatGPT 5