Problem Description

After solving tedious tasks, Mirko decides to play a game with his good friend Slavko.

They write a sequence of $n$ letters on a piece of paper. Each player takes turns forming a word by removing a single letter from the sequence and appending it to the end of their word. Mirko starts the first round. The game ends when there are no letters left in the sequence.

A word is considered more beautiful than another if it lexicographically precedes the other word. The player who has the more beautiful word at the end of the game wins. If both players have the same word, they both lose the round.

Mirko plays better than Slavko, so he decides to make it easier for Slavko by always choosing the rightmost letter from the sequence. Knowing this, Slavko wonders if he has a chance to win and what the most beautiful word he could possibly get is.

Input Format

The first line contains an integer $n$, as described in the problem statement.

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

Output Format

The first line should contain a capitalized string NE or DA. DA indicates that Slavko can win, and NE indicates that Slavko cannot win.

The second line should contain a string representing the most beautiful word Slavko could get.

Sample Input and Output

Sample Input #1

2
ne

Sample Output #1

NE
n

Sample Input #2

4
kava

Sample Output #2

DA
ak

Sample Input #3

8
cokolada

Sample Output #3

DA
acko

Notes

Data Size and Constraints

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

Additional Notes

• This problem is worth $80$ points.
• The problem is translated from COCI2010-2011 CONTEST #2 IGRA, translated by @mnesia.

见题面 Input 部分

见题面 Output 部分