DreamGrid 有一个包含 $n$ 个整数的数组。他可以在这个数组上执行以下操作：选择一个之前未被选中的元素，并将其标记为不可用。DreamGrid 希望执行恰好 $n$ 次操作，直到所有元素都被标记。

DreamGrid 将子数组的代价定义为该子数组中的逆序对数量。在执行每次操作之前，DreamGrid 想知道不包含任何不可用元素的子数组的最大代价。

回想一下，子数组 $a_l, a_{l+1}, \dots, a_{r-1}, a_r$ 是原数组的一个连续部分，其中 $1 \le l \le r \le n$。子数组 $a_l, a_{l+1}, \dots, a_{r-1}, a_r$ 中的逆序对是指满足 $l \le i < j \le r$ 且 $a_i > a_j$ 的下标对 $(i, j)$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。 第三行包含一个排列 $p_1, p_2, \dots, p_n$，表示按顺序选择进行操作的元素下标。

注意，该排列是加密的，你可以通过以下方法得到真实的排列： 令 $z_i$ 为第 $i$ 次操作前的答案。第 $i$ 次操作的实际下标为 $p_i \oplus z_i$，其中 $\oplus$ 是按位异或运算符。

保证所有 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个整数 $z_1, z_2, \dots, z_n$，用空格分隔，其中 $z_i$ 是第 $i$ 次操作前的答案。

请不要在每行末尾输出多余的空格，否则你的答案可能会被判定为错误！

样例

输入 1

3
5
4 3 1 1 1
5 4 5 3 1
10
9 7 1 4 7 8 5 7 4 8
21 8 15 5 9 2 4 5 10 6
15
4 8 8 1 12 1 10 14 7 14 2 9 13 10 3
37 19 23 15 7 2 10 15 2 13 4 5 8 7 10

输出 1

7 0 0 0 0
20 11 7 2 0 0 0 0 0 0
42 31 21 14 14 4 1 1 1 0 0 0 0 0 0

说明

每组测试数据解码后的排列分别为 $\{2, 4, 5, 3, 1\}$，$\{1, 3, 8, 7, 9, 2, 4, 5, 10, 6\}$ 以及 $\{15, 12, 2, 1, 9, 6, 11, 14, 3, 13, 4, 5, 8, 7, 10\}$。