cho.shBeautiful Word
Time limit1sMemory limit128 MBProblem
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.