Nim Game Winner

In this problem, two players – Charlie and Dave – play a card game that is equivalent to the classic game of Nim. There are ( n ) piles of cards, and each pile contains a certain number of cards. Players take turns removing any positive number of cards from a single pile. Charlie starts first. The objective is to force your opponent into a position where no moves are possible. Under optimal play, the outcome of the game can be determined by computing the ( \text{Nim sum} ) of all the piles. The formula for the Nim sum is given by: ( \text{Nim sum} = a_1 \oplus a_2 \oplus \cdots \oplus a_n ), where ( \oplus ) represents the bitwise XOR operation. If the Nim sum is non-zero, Charlie can force a win; otherwise, Dave will win. Your task is to determine the winner of the game. Output 1 if Charlie wins, otherwise output 0.

inputFormat

The first line contains a single integer ( n ) (( 1 \le n \le 10^5 )) representing the number of piles. The second line contains ( n ) space-separated integers ( a_1, a_2, \dots, a_n ) (( 1 \le a_i \le 10^9 )), where each ( a_i ) denotes the number of cards in the i-th pile.

outputFormat

Output a single integer: 1 if Charlie wins (i.e., if the Nim sum is non-zero) and 0 if Dave wins (i.e., if the Nim sum is zero).## sample

4
3 4 5 6

1