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.

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

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.

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.