Problem 3. Quantum Moochanics

USACO 2024 February Contest, Gold

在空闲时间，Bessie 喜欢涉猎实验物理。她最近发现了一对新的亚原子粒子，命名为

哞微子

和

反哞微子

。如同标准的

物质-反物质对

，哞微子和反哞微子相遇时会相互湮灭并消失。但这些粒子的独特之处在于，每当 Bessie 看向它们时它们就会改变运动方向（同时保持相同的速率）。

在她最新的实验中，Bessie 将

偶数

$N$（$2 \leq N \leq 2 \cdot 10^5$）个这些粒子排成一行。这一行的左端以哞微子开始，然后在两种类型的粒子之间交替，第 $i$ 个粒子位于位置 $p_i$（$0 \leq p_1 < \cdots < p_N \leq 10^{18}$）。哞微子初始时

向右

运动而反哞微子初始时

向左

运动，其中第 $i$ 个粒子以每秒 $s_i$ 单位的恒定速率运动（$1 \leq s_i \leq 10^9$）。

Bessie 在以下时刻进行观察：

• 首先是实验开始后 $1$ 秒。
• 然后是第一次观察后 $2$ 秒。
• 然后是第二次观察后 $3$ 秒。
• ……
• 然后是第 $n$ 次观察后 $n + 1$ 秒。

在每次观察中，Bessie 都会记下哪些粒子消失了。

这个实验可能需要非常长的时间才能完成，所以 Bessie 想要首先模拟一下它的结果。根据实验设置，请帮助 Bessie 求出她何时（即

观察次数

）会观察到各个粒子消失！可以证明，所有粒子最终都会消失。

输入格式（从终端 / 标准输入读入）：

每个测试点包含 $T$（$1\le T\le 10$）个独立的测试用例。

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

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

输出格式（输出至终端 / 标准输出）：

对于每一个测试用例，输出每个粒子消失时的观察次数，用空格分隔。

输入样例：

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

输出样例：

9 9
11 11
1 1
3 3

对于第一个测试用例，Bessie 在前 $8$ 次观察中观察到以下情况：

• 哞微子（初始时向右运动）出现在位置 $2 \rightarrow 0 \rightarrow 3 \rightarrow -1 \rightarrow 4 \rightarrow -2 \rightarrow 5 \rightarrow -3$。
• 反哞微子（初始时向左运动）出现在位置 $10 \rightarrow 12 \rightarrow 9 \rightarrow 13 \rightarrow 8 \rightarrow 14 \rightarrow 7 \rightarrow 15$。

然后恰好在观察 $9$ 时，两个粒子在位置 $6$ 相遇并相互湮灭。

对于第二个测试用例，反哞微子的初始位置更靠右 $1$ 单位，从而两个粒子在观察 $11$ 之前半秒在位置 $6.5$ 相遇。

注意我们只关心观察次数，不关心时刻或位置。

输入样例：

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

输出样例：

1 1 3 3
7 2 2 7

对于第一个测试用例：

• 最左边的两个粒子恰好在观察 $1$ 时在位置 $2$ 相遇。
• 最右边的两个粒子在观察 $3$ 之前半秒在位置 $6.5$ 相遇。

测试点性质： 测试点 3：$N = 2$。测试点 4：$N \leq 2000$，且对于所有粒子，$p_i \leq 10^4$。测试点 5-7：$N \leq 2000$。测试点 8-12：没有额外限制。

供题：Aryansh Shrivastava，Benjamin Qi