Odd Nim

Misha and Gleb are very fond of the famous game Nim. Here are its rules briefly:

• There are $N$ piles of stones on the table, and pile $i$ contains $a_i$ stones.
• Two players take turns. On each turn, a player must choose any non-empty pile and remove any nonzero number of stones from it.
• The player who cannot make a move loses.

Our heroes have played this game for so long that they found a winning strategy and can now determine the winner just by looking at the table. Having lost interest in it, they switched to giving-up Nim, which differs from the original only in that the player who cannot make a move is declared the winner.

The friends spent long evenings happily playing this new game until Vitya came and told them that the outcome of this game can also be predicted just by looking at the table.

Then the rules were made harder: now only an odd number of stones may be taken. This time Vitya could not find a strategy to stop the two friends, so he asked you for help. Write a program that determines the winner of Nim when only an odd number of stones may be taken from a pile. Just in case, also learn to determine the winner of giving-up Nim in which only an odd number of stones may be taken, since Vitya suspects that this game will be Gleb and Misha's next one.

Misha always moves first.

The first line contains a single integer $N$, $1 \le N \le 10^5$. The next line contains $N$ integers $a_i$, $1 \le a_i \le 10^9$.

On the first line, print the name of the winner when the player who cannot make a move loses. On the second line, print the name of the winner when the player who cannot make a move wins.