|
|
John was bored so after a while of thinking he invented a kind of game.
He took a piece of paper and wrote 0 and 1 on it. Then he took the
array he had already written and wrote a new array at the of it.
The appended array had the same length as the original one, but had
all 0's changed to 1's and 1's to 0's. So on the paper appeared 0110.
John repeated the operation and had 01101001 on his paper.
John started to wonder what number is on the 20th position. He
repeated the operation twice more (getting 01101001100101101001011001101001)
and found out that there is 1 on this position.
Then John wanted to know what is on 200th position. After a few minutes
of writing he knew it. But his young, curious mind made him wonder what
is on 2.000.000th or even 2.000.000.000th position. So he started eagerly
writing his arrays...
Unfortunatelly John did not realize that this way he would run out of paper
(and of life perhaps) before he could get to the solution.
Please, help John and introduce an effective way of solving his problem.
Input data
At the begining of input there is one positive integer d, which is foollowed by d integers (not less than 1 and not greater than 2.000.000.000) - positions that John is interested in.
Output data
On output write d integers (each in separate line) - numbers on specified positions in the array.
Input data example:
3 1 5 20
Output data for our example:
0 1 1