闲暇时，Bessie 喜欢涉猎实验物理。她最近发现了一对新的亚原子粒子，名为 mootrinos 和 antimootrinos。与普通的物质—反物质对一样，它们相遇时会相互湮灭并消失。然而，它们的独特之处在于，每当 Bessie 看着它们时，它们都会改变运动方向，同时保持速度大小不变。

在最新的实验中，Bessie 将偶数个 $N$（$2 \leq N \leq 2 \cdot 10^5$）这样的粒子放在一条直线上。最左边是 mootrino，此后两种粒子交替排列，第 $i$ 个粒子位于 $p_i$（$0 \leq p_1 < \cdots < p_N \leq 10^{18}$）。mootrinos 起初向右运动，antimootrinos 起初向左运动。第 $i$ 个粒子的恒定速度为每秒 $s_i$ 单位（$1 \leq s_i \leq 10^9$）。

Bessie 在以下时刻进行观测：

• 第一次，在实验开始 $1$ 秒后。
• 然后，在第一次观测 $2$ 秒后。
• 然后，在第二次观测 $3$ 秒后。
• ...
• 然后，在第 $n$ 次观测 $n + 1$ 秒后。

每次观测时，Bessie 记录哪些粒子已经消失。

实验可能需要极长时间才能结束，因此 Bessie 想先模拟结果。给定实验设置，请帮助她确定何时（即第几次观测）会发现每个粒子消失！可以证明所有粒子最终都会消失。

输入格式

每份输入包含 $T$（$1\le T\le 10$）个独立测试用例。

每个测试用例有三行：第一行包含 $N$，第二行包含 $p_1,\dots,p_N$，第三行包含 $s_1\dots,s_N$。

保证所有 $N$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每个测试用例，输出每个粒子消失时的观测编号，以空格分隔。

样例

输入格式 1

4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5

输出格式 1

9 9
11 11
1 1
3 3

说明

第一个测试用例中，前 $8$ 次观测如下：

• mootrino（最初向右运动）出现在位置 $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$。
• antimootrino（最初向左运动）出现在位置 $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$。

随后，恰好在第 $9$ 次观测时，两粒子在 $6$ 处相遇并相互湮灭。

第二个测试用例中，antimootrino 的起点向右多了 $1$ 单位，所以两个粒子在第 $11$ 次观测前半秒于 $6.5$ 处相遇。

注意，我们只关心观测编号，不关心时刻或位置。

输入格式 2

2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 1

输出格式 2

1 1 3 3
7 2 2 7

说明

对于第一个测试用例：

• 最左边的两个粒子恰好在第 $1$ 次观测时于 $2$ 处相遇。
• 最右边的两个粒子在第 $3$ 次观测前半秒于 $6.5$ 处相遇。

子任务

• 输入三满足 $N = 2$。
• 输入四满足 $N \leq 2000$，且对于所有奶牛有 $p_i \leq 10^4$。
• 输入五至七满足 $N \leq 2000$。
• 输入八至十二没有额外限制。

题目作者：Aryansh Shrivastava、Benjamin Qi