Svetozar 有一个包含 $n$ 个整数的数组 $a$。他为这个数组设计了几种操作：

• $1$：将 $a$ 替换为数组 $a$ 的前缀异或和数组。 这意味着操作后数组的第 $i$ 个元素将变为 $a_1 \oplus a_2 \oplus \dots \oplus a_i$。
• $2$：将 $a$ 替换为数组 $a$ 的后缀异或和数组。 这意味着操作后数组的第 $i$ 个元素将变为 $a_i \oplus a_{i+1} \oplus \dots \oplus a_n$。
• $-1$：执行操作 $1$ 的逆操作。 这意味着数组元素的变化方式使得如果随后对数组应用操作 $1$，得到的结果数组将与执行操作 $-1$ 之前的数组相同。
• $-2$：执行操作 $2$ 的逆操作。 这意味着数组元素的变化方式使得如果随后对数组应用操作 $2$，得到的结果数组将与执行操作 $-2$ 之前的数组相同。

Svetozar 执行了一系列操作，现在请你检查他计算结果的正确性。为了简化验证，Svetozar 执行的第一次操作总是用正数表示，且任意两个连续操作的符号不同。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。 接下来是 $T$ 个测试用例的描述，每个描述包含三行。 每个描述的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示数组的大小和操作的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)，表示数组的元素。 第三行包含 $q$ 个整数 $op_1, op_2, \dots, op_q$ ($-2 \le op_i \le 2, op_i \neq 0, op_1 > 0, op_i \cdot op_{i+1} < 0$)，表示按顺序执行的操作。

保证所有测试用例中 $n$ 的总和不超过 $10^5$，且所有测试用例中 $q$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，在单独的一行中输出 $n$ 个整数：应用所有操作后的数组。

样例

输入 1

3
5 1
0 1 2 4 8
1
7 2
25 2 20 23 998 244 353
2 -2
9 9
9 9 8 2 4 4 3 5 3
2 -1 2 -1 2 -1 2 -1 2

输出 1

0 1 3 7 15
25 2 20 23 998 244 353
4 7 2 1 14 7 14 6 4