Description

Dream has an integer array $a_1,a_2,\dots,a_n$ of length $n$ ($1\le n\le 10^5$). For $i=1,2,\dots,n$, it holds that $0\le a_i<2^{60}$.

He computed the prefix XOR array $p_i=a_1\oplus a_2\oplus\dots\oplus a_i$ and the suffix XOR array $s_i=a_i\oplus a_{i+1}\oplus\dots\oplus a_n$.

Now Tommy has replaced a total of $n$ elements in $p$ and $s$ with $-1$. Given the current arrays $p$ and $s$, restore any possible array $a_1,a_2,\dots,a_n$.

It is guaranteed that a valid solution exists.

Input Format

This problem contains multiple test cases. The first line contains a positive integer $t$, the number of test cases. Then follow $t$ test cases. For each test case:

The first line contains a positive integer $n$ ($1\le n\le 10^5$).

The next line contains $n$ integers $p_1,p_2,\dots,p_n$.

The next line contains $n$ integers $s_1,s_2,\dots,s_n$.

Output Format

For each test case:

Output $n$ non-negative integers $a_1,a_2,\dots,a_n$ that satisfy the above conditions.

1
4
-1 34 367 -1
3178 -1 -1 3333

3 33 333 3333

Hint

For $100\%$ of the testdata, $1\le n,\sum n\le 10^5$, $\sum [p_i=-1]+\sum [s_i=-1]=n$, and a valid solution is guaranteed to exist.

• Subtask 1 (10 pts): $n\le 4$, $p_i,s_i<2$.
• Subtask 2 (10 pts): $n\le 100$.
• Subtask 3 (20 pts): $p_i,s_i<2$.
• Subtask 4 (60 pts): No special constraints.

Translated by ChatGPT 5