Description

在闲暇时，贝西喜欢涉足实验物理。她最近发现了一对新的亚原子粒子，命名为mootrinos和antimootrinos。

与标准物质-反物质对一样，当它们相遇时，mootrinos和antimootrinos会相互湮灭并消失。但使这些粒子独特的是，每当贝西看着它们时，它们会改变运动方向（同时保持相同的速度）。

对于她最新的实验，贝西在一条线上放置了偶数个这些粒子$N\left(2 \leq N \leq 2 \cdot 10^5\right)$。该线以左侧的一个mootrino开始，然后在两种类型的粒子之间交替，第$i$个粒子位于位置$p_i$（$0 \leq p_1<\cdots<p_N \leq 10^{18}$）。mootrinos最初向右移动，而antimootrinos最初向左移动，并且第$i$个粒子以$s_i$单位每秒的恒定速度移动$\left(1 \leq s_i \leq 10^9\right)$。

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

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

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

输入格式：

每个输入包含$T(1 \leq T \leq 10)$个独立的测试用例。 每个测试用例由三行组成。第一行包含$N$，第二行包含$p_1, \ldots, p_N$，第三行包含$s_1, \ldots, s_N$。

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

输出格式：

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

Samples

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

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$，并且对所有牛$pi \leq 10^4$。
• 输入5-7满足$N \leq 2000$。
• 输入8-12没有额外的约束。