CF1922D.Berserk Monsters

Monocarp is playing a computer game (yet again). Guess what is he doing? That's right, killing monsters.

There are $n$ monsters in a row, numbered from $1$ to $n$. The $i$-th monster has two parameters: attack value equal to $a_i$ and defense value equal to $d_i$. In order to kill these monsters, Monocarp put a berserk spell on them, so they're attacking each other instead of Monocarp's character.

The fight consists of $n$ rounds. Every round, the following happens:

• first, every alive monster $i$ deals $a_i$ damage to the closest alive monster to the left (if it exists) and the closest alive monster to the right (if it exists);
• then, every alive monster $j$ which received more than $d_j$ damage during this round dies. I. e. the $j$-th monster dies if and only if its defense value $d_j$ is strictly less than the total damage it received this round.

For each round, calculate the number of monsters that will die during that round.

Monocarp 正在玩一款电脑游戏（又一次）。猜猜他在干什么？没错，就是在打怪。

一共有 $n$ 只怪物排成一列，编号从 $1$ 到 $n$。第 $i$ 只怪物有两个参数：攻击力为 $a_i$，防御力为 $d_i$。为了消灭这些怪物，Monocarp 对它们施加了一个狂暴咒语，因此它们转而互相攻击，而非攻击 Monocarp 的角色。

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

• 首先，每个尚存的怪物 $i$ 向其左侧最近的尚存怪物（若存在）和右侧最近的尚存怪物（若存在）各造成 $a_i$ 点伤害；
• 然后，所有在本轮中受到的总伤害严格大于其防御力 $d_j$ 的尚存怪物 $j$ 将死亡。即：第 $j$ 只怪物死亡当且仅当其防御力 $d_j$ 严格小于它在本轮中受到的总伤害。

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

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$);
• the third line contains $n$ integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$).

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print $n$ integers. The $i$-th integer should be equal to the number of monsters that die during the $i$-th round.

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

Explanation for the first test case of the example:

During the first round, the following happens:

• the monster $1$ deals $3$ damage to the monster $2$;
• the monster $2$ deals $4$ damage to the monster $1$ and the monster $3$;
• the monster $3$ deals $7$ damage to the monster $2$ and the monster $4$;
• the monster $4$ deals $5$ damage to the monster $3$ and the monster $5$;
• the monster $5$ deals $10$ damage to the monster $4$;
• the monster $1$ does not die, since it received $4$ damage and its defense is $4$;
• the monster $2$ dies, since it received $10$ damage and its defense is $9$;
• the monster $3$ dies, since it received $9$ damage and its defense is $1$;
• the monster $4$ does not die, since it received $17$ damage and its defense is $18$;
• the monster $5$ dies, since it received $5$ damage and its defense is $1$.

After the first round, the monsters $1$ and $4$ stay alive.

During the second round, the following happens:

• the monster $1$ deals $3$ damage to the monster $4$;
• the monster $4$ deals $5$ damage to the monster $1$;
• the monster $1$ dies, since it received $5$ damage and its defense is $4$;
• the monster $4$ does not die, since it received $3$ damage and its defense is $18$.

During the next three rounds, only the $4$-th monster is alive, so nothing happens.

示例中第一个测试用例的解释：

在第一轮中，发生以下情况：

• 怪物 $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$ 号怪物存活，因此不发生任何事件。