Migrated from Lutece 500 IGRA

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Having solved the tedious assignment, Mirko decided to play a game with his good friend Slavko.

They have written a sequence of $N$ letters on a piece of paper. Each one of them is trying to put together a word using letters from the sequence. They alternate taking turns consisting of removing a single letter from the sequence and appending it to the end of their word. Mirko has the first turn. The game ends when no letters are remaining in the sequence.

We define a word to be more beautiful than another word if it comes first alphabetically. The player who has the more beautiful word at the end of the game wins. If both players have equal words, they both lose.

Mirko is a much better player than Slavko, so he has decided to make it easier for Slavko by always selecting the rightmost remaining letter in the sequence. Knowing this, Slavko wants to find out if it is possible for him to win and which is the most beautiful word he can end the game with.

Input

The first line of input contains an even positive integer $N$ ($2 \leq N \leq 100 000$).

The second line of input contains $N$ characters, the starting letter sequence. All characters are lower case letters from the English alphabet.

Output

The first line of output must contain DA if it is possible for Slavko to win, and NE otherwise.

The second line of output must contain the most beautiful word that Slavko can have at the end of the game.

Samples

2 
ne

NE 
n

4 
kava

DA 
ak

8 
cokolada

DA 
acko

Note

In test cases worth $50\%$ of total points the number $N$ will not exceed $1000$.

Resources

COCI 2010/2011, 2nd round, November 13th 2010, Author: Goran Gašić