Ironman and Thanos are playing the game of Infinity Xor with an array of non-negative integers. They take alternate turns.
Let the size of the array at the beginning of each turn be n. Initially n=N=2x ,where x is some non-negative integer . During a player's turn he can choose any n/2 elements from the array such that their XOR is Odd and discard the remaining n/2 elements. The new array for the next turn contains the n/2 elements chosen in this turn.
A player loses if n is odd or if he cannot choose n/2 elements such that their XOR is Odd. Decide the winner if both the players play optimally. Ironman plays first.
Input:
Output:
Constraints: