G. I am Tired of Xor Problems
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays $$$a$$$ and $$$b$$$ of size $$$n$$$. Consider a sequence $$$c$$$ of length $$$n$$$ such that for each $$$i$$$ from $$$1$$$ to $$$n$$$, you can choose $$$c_i$$$ from either $$$a_i$$$ or $$$b_i$$$. Let $$$f(k)$$$ be the maximum of $$$c_1 \oplus c_2 \oplus \cdots \oplus c_n$$$ if you can choose at most $$$k$$$ values from the array $$$a$$$. Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Find the value of $$$f(k)$$$ for each $$$k$$$ from $$$0$$$ to $$$n$$$.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^5$$$) – the number of test cases.

Each test case consists of three lines. The first line contains an integer $$$n$$$ ($$$1 \le n \le 2^{20}$$$). The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt n$$$). The third line contains $$$n$$$ space-separated integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \lt n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2^{20}$$$.

Output

For each test case, print $$$n + 1$$$ space-separated integers $$$f(0), f(1), f(2), \ldots, f(n)$$$.

Example
Input
3
4
1 2 2 2
3 0 0 3
3
0 0 0
0 0 0
2
0 1
1 1
Output
0 2 3 3 3 
0 0 0 0 
0 1 1
Note

In the first test case,

  • $$$f(0) = b_1 \oplus b_2 \oplus b_3 \oplus b_4 = 3 \oplus 0 \oplus 0 \oplus 3 = 0$$$, here we can not choose any element from $$$a$$$
  • $$$f(1) = b_1 \oplus a_2 \oplus b_3 \oplus b_4 = 3 \oplus 2 \oplus 0 \oplus 3 = 2$$$, here we select $$$1$$$ element from $$$a$$$. Note that there are multiple ways to select at most $$$1$$$ element from $$$a$$$ and out of all the ways, the maximum xor value is $$$2$$$.
  • $$$f(2) = a_1 \oplus b_2 \oplus b_3 \oplus a_4 = 1 \oplus 0 \oplus 0 \oplus 2 = 3$$$, here we select $$$2$$$ elements from $$$a$$$.
  • $$$f(3) = b_1 \oplus b_2 \oplus a_3 \oplus a_4 = 3 \oplus 0 \oplus 2 \oplus 2 = 3$$$, here we select $$$2$$$ elements from $$$a$$$. Note that we don't have to select exactly $$$k$$$ elements from $$$a$$$, the condition is that we can select at most $$$k$$$ elements from $$$a$$$.
  • $$$f(4) = a_1 \oplus a_2 \oplus a_3 \oplus a_4 = 1 \oplus 2 \oplus 2 \oplus 2 = 3$$$, here we select $$$4$$$ elements from $$$a$$$.

In the third test case,

  • $$$f(0) = b_1 \oplus b_2 = 1 \oplus 1 = 0$$$
  • $$$f(1) = a_1 \oplus b_2 = 0 \oplus 1 = 1$$$
  • $$$f(2) = a_1 \oplus a_2 = 0 \oplus 1 = 1$$$