D. 狂暴怪物

时间限制：每个测试 $2$ 秒
内存限制：每个测试 $256$ MB

Monocarp 又在玩电脑游戏了。猜猜他在做什么？没错，杀怪物。

有 $n$ 个怪物排成一排，编号从 $1$ 到 $n$。第 $i$ 个怪物有两个参数：攻击力 $a_i$ 和防御力 $d_i$。为了杀死这些怪物，Monocarp 对它们施放了狂暴咒语，于是它们开始互相攻击，而不是攻击 Monocarp 的角色。

战斗共进行 $n$ 轮。每一轮会发生以下事件：

• 首先，每个存活的怪物 $i$ 会对左边最近的存活怪物（如果存在）和右边最近的存活怪物（如果存在）各造成 $a_i$ 点伤害；
• 然后，在本轮中受到的总伤害严格大于其防御力 $d_j$ 的存活怪物 $j$ 会死亡。即，第 $j$ 个怪物死亡当且仅当 $d_j <$ 本轮它受到的伤害总和。

对于每一轮，请计算该轮中死亡的怪物数量。

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例由三行组成：

• 第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）；
• 第三行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$（$1 \le d_i \le 10^9$）。

附加输入限制：所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

输出

对于每个测试用例，输出 $n$ 个整数。第 $i$ 个整数应等于第 $i$ 轮中死亡的怪物数量。

样例

输入

3
5
3 4 7 5 10
4 9 1 18 1
2
2 1
1 3
4
1 1 2 4
3 3 4 2

输出

3 1 0 0 0 
0 0 
1 1 1 0 

说明

以第一个测试用例为例：

第一轮发生以下情况：

• 怪物 $1$ 对怪物 $2$ 造成 $3$ 点伤害；
• 怪物 $2$ 对怪物 $1$ 和怪物 $3$ 各造成 $4$ 点伤害；
• 怪物 $3$ 对怪物 $2$ 和怪物 $4$ 各造成 $7$ 点伤害；
• 怪物 $4$ 对怪物 $3$ 和怪物 $5$ 各造成 $5$ 点伤害；
• 怪物 $5$ 对怪物 $4$ 造成 $10$ 点伤害；
• 怪物 $1$ 未死亡，因受到 $4$ 点伤害而防御为 $4$；
• 怪物 $2$ 死亡，因受到 $10$ 点伤害而防御为 $9$；
• 怪物 $3$ 死亡，因受到 $9$ 点伤害而防御为 $1$；
• 怪物 $4$ 未死亡，因受到 $17$ 点伤害而防御为 $18$；
• 怪物 $5$ 死亡，因受到 $5$ 点伤害而防御为 $1$。

第一轮后，怪物 $1$ 和 $4$ 存活。

第二轮发生以下情况：

• 怪物 $1$ 对怪物 $4$ 造成 $3$ 点伤害；
• 怪物 $4$ 对怪物 $1$ 造成 $5$ 点伤害；
• 怪物 $1$ 死亡，因受到 $5$ 点伤害而防御为 $4$；
• 怪物 $4$ 未死亡，因受到 $3$ 点伤害而防御为 $18$。

接下来的三轮中，仅剩怪物 $4$ 存活，因此无事发生。