Beautiful Word

Time limit1sMemory limit128 MB

Summary

Simulate a turn-based letter-picking game where one player greedily takes the rightmost slip while the other picks optimally to form the lexicographically smallest possible word, then compare outcomes.

Level: Hard8 of 10
Topics: Greedy, Game theory, String
Solved: No attempts yet

Problem

Sanggeun and Heewon play a game with paper slips arranged in one row. Each slip has one lowercase English letter on it. The players alternate turns taking one slip, appending its letter to the end of the word they are building. Sanggeun starts first, and the game ends when no slips remain.

Between two words, the word that comes earlier in lexicographic order is considered more beautiful. If the two words are equal, neither player wins.

Sanggeun always takes the rightmost remaining slip. Heewon knows this, and on each of her turns she may take any one remaining slip. Determine whether Heewon can beat Sanggeun, and find the most beautiful word Heewon can make.

Input

The first line contains an even integer N. (2 <= N <= 100000)

The second line contains a string of length N, describing the initial slips from left to right. Every character is a lowercase English letter.

Output

If Heewon can make a word that is lexicographically smaller than Sanggeun's word, print DA on the first line. Otherwise, print NE.

On the second line, print the most beautiful word Heewon can make.

Examples3

Example 1
Input
```
2
ne
```
Expected output
```
NE
n
```
Example 2
Input
```
4
kava
```
Expected output
```
DA
ak
```
Example 3
Input
```
8
cokolada
```
Expected output
```
DA
acko
```