Battle#11768
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 of length and an array . For each 1 \le i \le n find the biggest integer such that there exists an integer 0 \leq g \leq y_i for which, in an array of length , where b_j = a_j \oplus g, all numbers from to m-1 (inclusive) appear among b_1, \dots, b_i.
Here, means bitwise XOR operation.
The first line contains an integer n(1 \le n \le 3\cdot10^5).
The second line contains integers a_i(0 \le a_i < 2^{30}) — the elements of the array.
The third line contains integers y_i(0 \le y_i < 2^{30}).
Output integers separated by a space — the solution to the problem for each from to .
Example 1
Example 2
In the second sample:
for i = 1 we can choose y = 100, then our prefix will be: [100 \oplus 100] = [0] — is .
for i = 2 we can choose y = 0, then our prefix will be: [100 \oplus 0, 102 \oplus 0] = [100,102] — is .
for i = 2 we can choose y = 100, then our prefix will be: [100 \oplus 100, 102 \oplus 100, 103 \oplus 100] = [0,2,3] — is .
for i = 2 we can choose y = 101, then our prefix will be: [100 \oplus 101, 102 \oplus 101, 103 \oplus 101, 101 \oplus 101] = [1,3,2,0] — is .
for i = 2 we can choose y = 102, then our prefix will be: [100 \oplus 102, 102 \oplus 102, 103 \oplus 102, 101 \oplus 102,104 \oplus 102] = [2,0,1,3,14] — is .
( points): n \le 100, a_i < 2^7, y_i < 2^7;
( points): n \le 3000, a_i < 2^{10}, y_i < 2^{10};
( points): n \le 3000;
( points): y_i = 2^{30}-1;
( points): no additional constraints;