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:
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:
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.
353 4 7 5 104 9 1 18 122 11 341 1 2 43 3 4 2
3 1 0 0 0 0 0 1 1 1 0
Explanation for the first test case of the example:
During the first round, the following happens:
After the first round, the monsters $$$1$$$ and $$$4$$$ stay alive.
During the second round, the following happens:
During the next three rounds, only the $$$4$$$-th monster is alive, so nothing happens.
Name |
---|