Battle

And so the battle erupted. You exchange spells, destroy planets, and tear apart the very fabric of reality. But so far, no one has managed to find a way to breach the opponent's defenses. Wizard Frusi taught you a spell capable of breaking through any defense, but the cautious Chmyaaax placed a limiter on you specifically designed to block that spell. Unfortunately, due to a lack of time, you did not manage to learn how to counter such a trick, but you remember that you need to know the key, which can be obtained as the answer to the following task:

Given an array $a$ of length $n$ and an array $y$. For each $1\le i\le n$ find the biggest integer $m$ such that there exists an integer $0\le g\le y_i$ for which, in an array $b$ of length $i$, where $b_j=a_j\oplus g$, all numbers from $0$ to $m-1$ (inclusive) appear among $b_1,\dots ,b_i$.

Here, $\oplus$ means bitwise XOR operation.

Input

The first line contains two integers $n(1\le n\le 3\cdot 10^5)$.

The second line contains $n$ integers $a_i(0\le a_i<2^{30})$ — the elements of the array.

The third line contains $n$ integers $y_i(0\le y_i<2^{30})$.

Output

Output $n$ integers separated by a space — the solution to the problem for each $i$ for 1 to $n$.

Examples

Note

In the second sample:

1. for $i=1$ we can choose $y=100$, then our preffix wiil be: $[100\oplus 100]=[0]$ — $m$ is $1$.

2. for $i=2$ we can choose $y=0$, then our preffix wiil be: $[100\oplus 0,102\oplus 0]=[100,102]$ — $m$ is $0$.

3. for $i=2$ we can choose $y=100$, then our preffix wiil be: $[100\oplus 100,102\oplus 100,103\oplus 100]=[0,2,3]$ — $m$ is $1$.

4. for $i=2$ we can choose $y=101$, then our preffix wiil be: $[100\oplus 101,102\oplus 101,103\oplus 101,101\oplus 101]=[1,3,2,0]$ — $m$ is $4$.

5. for $i=2$ we can choose $y=102$, then our preffix wiil be: $[100\oplus 102,102\oplus 102,103\oplus 102,101\oplus 102,104\oplus 102]=[2,0,1,3,14]$ — $m$ is $4$.

Scoring

1. ($9$ points): $n\le 100,a_i<2^7,y_i<2^7$;

2. ($17$ points): $n\le 3000,a_i<2^{10},y_i<2^{10}$;

3. ($31$ points): $n\le 3000$;

4. ($41$ points): $y_i=2^{30}-1$;

5. ($77$ points): no additional constraints;