print1603. Game

printGame

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
The first line of input contains an even positive integer `N` (`2\ ≤\ N\ ≤\ 100\ 000`). The second line of input contains `N` characters, the starting letter sequence. All characters are lower case letters from the English alphabet.
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.

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
Source: COCI 2010/2011, contest #2
loading