A sequence $S$ is defined as below:

$S_1 = \{ 1 \}$

$S_2 = S_1 + \{ 2 \} + S_1 = \{ 1,2,1 \}$

$S_3 = S_2 + \{ 3 \} + S_2 = \{ 1,2,1,3,1,2,1 \}$

...

$S_i = S_{i-1} + \{ i \} + S_{i-1}$

where $+$ means concatenation.

Now there is a number $x$, $x$ is initially $1$.

Given $N$ operation, which are of $2$ types:

Type $1$, $x := x+1$
Type $2$, $x := 2x$

Let $F(i)$ be the frequency of the the number $i$ in the first $x$ numbers of $S_{10^{10^9}}$ mod $10^9+7$.

Find $F(1)\oplus F(2)\oplus ... \oplus F(10^{10^9})$ after each operation, where $\oplus$ means XOR.

Input

On line 1, an integer $N$.

On line 2, $N$ integers, the $i$-th integer is $t_{i}$, the type of the $i$-th operation.

Output

Output $N$ numbers, the $i$-th number should be the desired answer after the $i$-th operation.

Subtasks

For all cases,
$1 \le N \le 10^6$

Subtask $1$ ($10$ pts): There are only type $1$ operations.
Subtask $2$ ($17$ pts): There are only type $2$ operations.
Subtask $3$ ($14$ pts): All type $1$ operations are after type $2$ operations.
Subtask $4$ ($24$ pts): There are no consecutive type $1$ operations.
Subtask $5$ ($16$ pts): There are at most $10$ type $1$ operations.
Subtask $6$ ($19$ pts): No Additional Constraints.