当前没有测试数据。

一、题目名称

量子哞力学（Quantum Moochanics）

二、题目描述

在闲暇时间，贝西（Bessie）喜欢涉足实验物理学。她最近发现了一对新的亚原子粒子，名为哞微子（mootrinos）和反哞微子（antimootrinos）。就像标准的物质 - 反物质对一样，哞微子和反哞微子相遇时会相互湮灭并消失。但这些粒子的独特之处在于，每当贝西观察它们时，它们会改变运动方向（同时保持相同速度）。

在她最近的实验中，贝西将偶数个$N$（$2\leq N\leq2\cdot10^5$）个这样的粒子排成一行。这一行从左边的一个哞微子开始，然后两种类型的粒子交替排列，第$i$个粒子位于位置$p_i$（$0\leq p_1<\cdots<p_N\leq10^{18}$）。哞微子最初向右移动，而反哞微子最初向左移动，第$i$个粒子以每秒$s_i$单位的恒定速度移动（$1\leq s_i\leq10^9$）。

贝西在以下时间进行观察：

1. 首先，在实验开始后$1$秒。
2. 然后在第一次观察后$2$秒。
3. 接着在第二次观察后$3$秒。
4. ……
5. 然后在第$n$次观察后$n + 1$秒。

在每次观察中，贝西记录下哪些粒子消失了。

这个实验可能需要极长的时间才能完成，所以贝西想先模拟其结果。给定实验设置，帮助贝西确定她将在何时（即观察次数）观察到每个粒子消失！可以证明所有粒子最终都会消失。

三、输入格式（从终端/标准输入读取）

1. 每个输入包含$T$（$1\leq T\leq10$）个独立的测试用例。
2. 每个测试用例由三行组成。第一行包含$N$，第二行包含$p_1,\cdots,p_N$，第三行包含$s_1,\cdots,s_N$。
3. 保证所有$N$的总和不超过$2\cdot10^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$次观察中观察到以下情况：

• 哞微子（最初向右移动）出现在位置$2\rightarrow0\rightarrow3\rightarrow - 1\rightarrow4\rightarrow - 2\rightarrow5\rightarrow - 3$。
• 反哞微子（最初向左移动）出现在位置$10\rightarrow12\rightarrow9\rightarrow13\rightarrow8\rightarrow14\rightarrow7\rightarrow15$。 然后在第$9$次观察时，两个粒子在位置$6$相遇并湮灭。 对于第二个测试用例，反哞微子起始位置向右多了$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$相遇。

六、评分规则

1. 输入3满足$N = 2$。
2. 输入4满足$N\leq2000$且对于所有粒子$p_i\leq10^4$。
3. 输入5 - 7满足$N\leq2000$。
4. 输入8 - 12满足无其他额外约束。

题目来源：Aryansh Shrivastava，Benjamin Qi。