题目描述

Dream 有一个长度为 $n$（$1\le n\le 10^5$）的整数数组 $a_1,a_2,\dots,a_n$，其中对于 $i=1,2,\dots,n$，满足 $0\le a_i<2^{60}$。

他计算了前缀异或数组 $p_i=a_1\oplus a_2\oplus\dots\oplus a_i$ 以及后缀异或数组 $s_i=a_i\oplus a_{i+1}\oplus\dots\oplus a_n$。

现在 Tommy 一共将 $p$ 和 $s$ 的 $n$ 个元素换成 $-1$。给定当前的 $p$ 与 $s$ 数组，请恢复任意一组可能为原数组的 $a_1,a_2,\dots,a_n$。

保证存在一组合法解。

输入格式

本题有多组数据，第一行一个正整数 $t$，为数据组数。接下来 $t$ 组数据，其中对于每一组数据：

第一行一个正整数 $n$（$1\le n\le 10^5$）。

接下来 $n$ 个整数 $p_1,p_2,\dots,p_n$。

接下来 $n$ 个整数 $s_1,s_2,\dots,s_n$。

输出格式

对于每一组数据：

输出 $n$ 个非负整数 $a_1,a_2,\dots,a_n$，满足以上条件。

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

3 33 333 3333

提示

对于 $100\%$ 的数据，$1\le n,\sum n\le 10^5$，$\sum [p_i=-1]+\sum [s_i=-1]=n$，保证有合法解。

• 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）：无特殊限制。