311022: CF1922D. Berserk Monsters

D. Berserk Monsterstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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$.

Output

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.

ExampleInput

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

Output

3 1 0 0 0 
0 0 
1 1 1 0 

Note

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.

**题目大意：**

题目描述了一个游戏场景，其中Monocarp在游戏中对一排怪物施放了一个狂战士法术，使得这些怪物相互攻击而不是攻击Monocarp的角色。游戏分为n轮，每一轮中，每个存活的怪物会对它左右两边最近的存活的怪物造成攻击伤害。之后，每个在这一轮中受到的伤害超过其防御值的怪物会死亡。对于每一轮，需要计算在这一轮中会死亡的怪物数量。

**输入数据格式：**

输入包含多个测试用例。每个测试用例的第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。每个测试用例包含三行：

- 第一行包含一个整数n（1 ≤ n ≤ 3 × 10^5），表示怪物的数量。
- 第二行包含n个整数a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^9），分别表示每个怪物的攻击值。
- 第三行包含n个整数d_1, d_2, …, d_n（1 ≤ d_i ≤ 10^9），分别表示每个怪物的防御值。

所有测试用例的n之和不超过3 × 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点伤害。在这一轮中，怪物2、怪物3和怪物5死亡，因为它们受到的伤害超过了它们的防御值。
- 第二轮中，只有怪物1和怪物4存活。怪物1对怪物4造成3点伤害，怪物4对怪物1造成5点伤害。在这一轮中，怪物1死亡。
- 在接下来的三轮中，只有怪物4存活，因此没有怪物死亡。**题目大意：** 题目描述了一个游戏场景，其中Monocarp在游戏中对一排怪物施放了一个狂战士法术，使得这些怪物相互攻击而不是攻击Monocarp的角色。游戏分为n轮，每一轮中，每个存活的怪物会对它左右两边最近的存活的怪物造成攻击伤害。之后，每个在这一轮中受到的伤害超过其防御值的怪物会死亡。对于每一轮，需要计算在这一轮中会死亡的怪物数量。 **输入数据格式：** 输入包含多个测试用例。每个测试用例的第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。每个测试用例包含三行： - 第一行包含一个整数n（1 ≤ n ≤ 3 × 10^5），表示怪物的数量。 - 第二行包含n个整数a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^9），分别表示每个怪物的攻击值。 - 第三行包含n个整数d_1, d_2, …, d_n（1 ≤ d_i ≤ 10^9），分别表示每个怪物的防御值。 所有测试用例的n之和不超过3 × 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点伤害。在这一轮中，怪物2、怪物3和怪物5死亡，因为它们受到的伤害超过了它们的防御值。 - 第二轮中，只有怪物1和怪物4存活。怪物1对怪物4造成3点伤害，怪物4对怪物1造成5点伤害。在这一轮中，怪物1死亡。 - 在接下来的三轮中，只有怪物4存活，因此没有怪物死亡。