P6548 [COCI 2010/2011 #2] IGRA

After finishing a tedious task, Mirko decided to play a game with his good friend Slavko. They write a sequence of $n$ letters on a sheet of paper. Each player takes turns using the letters in the sequence to spell a word: on each turn, they remove one letter from the sequence and append it to the end of their word. Mirko takes the first turn. The game ends when there are no letters left in the sequence. One word is considered more beautiful than another if it comes earlier in lexicographical order. At the end of the game, the player with the more beautiful word wins. If both players' words are the same, then both of them lose that round. Mirko plays better than Slavko, so he decided to make it easier for Slavko by always choosing the rightmost letter in the sequence. Knowing this, Slavko wants to know whether it is possible for him to win, and what the most beautiful word he can obtain is.

The first line contains an integer $n$, whose meaning is described above. The second line contains a string of length $n$, representing the initial sequence.

The first line contains an uppercase string `NE` or `DA`. `DA` means Slavko can possibly win, and `NE` means Slavko cannot win. The second line contains a string, the most beautiful word Slavko can possibly obtain.

#### Constraints - For $50\%$ of the testdata, $n = 2\times k(1 \leq k \leq 500)$ and $k$ is an integer. - For $100\%$ of the testdata, $n = 2\times k(1 \leq k \leq 10^5)$ and $k$ is an integer. All characters in the input and in the second output line are lowercase letters. #### Notes - The full score for this problem is $80$ points. - Translated from [COCI2010-2011](https://hsin.hr/coci/archive/2010_2011/) [CONTEST #2](https://hsin.hr/coci/archive/2010_2011/contest2_tasks.pdf) IGRA. Translator: @[mnesia](https://www.luogu.com.cn/user/115711)。 Translated by ChatGPT 5