To play or not to play P56691

Consider a two-player game based (as it is so common) on a movie where people die. The game, alternating turns, has two phases, the first for arming, the second for killing.

During the first phase some arsenals appear, each with several weapons. At every turn, at least one weapon must be taken. On the first turn, player 1 chooses one arsenal, and takes from it as many weapons as he wants. Then, alternately, if the arsenal of the previous turn was not emptied, the weapons must be taken from the same arsenal. Otherwise, any non-empty arsenal can be chosen. This phase ends when all arsenals are empty.

The slaughter would begin after the arming phase, but unfortunately the player to starts the second phase always loses. (This is due to a bug in the code of a guy who claims that compiling with -Wall is silly.) Therefore, the last to take arms during the first phase always wins the game.

Write a program that, given the number of weapons of every arsenal, tells who wins a game assuming perfect play by both players.

Input

Input consists of several cases. Every case begins with a number n ≤ 10⁵, followed by n numbers between 1 and 10⁹ to indicate the number of weapons of each arsenal.

Output

For every case, tell who wins the game.

(Explanation of the first case: On the first turn, player 1 chooses for instance the third arsenal, and takes one weapon. On the the second turn, player 2 must take the only weapon left in the same arsenal. On the third turn, player 1 takes all the weapons of the second arsenal. On the the fourth turn, player 2 takes for instance the only weapon of the first arsenal. On the fifth turn, player 1 takes the only weapon left. On the sixth turn, player 2 loses because he cannot take any weapon.)