Монокарп играет в компьютерную игру (опять). Угадайте, что он делает? Правильно, убивает монстров.
В ряд стоят $$$n$$$ монстров, пронумерованных от $$$1$$$ до $$$n$$$. У $$$i$$$-го монстра есть два параметра: значение атаки, равное $$$a_i$$$, и значение защиты, равное $$$d_i$$$. Чтобы убить этих монстров, Монокарп наложил на них заклинание безумия, так что они атакуют друг друга, а не персонажа Монокарпа.
Бой состоит из $$$n$$$ раундов. В каждом раунде происходит следующее:
Для каждого раунда вычислите количество монстров, которые умрут во время этого раунда.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Каждый набор состоит из трех строк:
Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ целых чисел. $$$i$$$-е целое число должно быть равно количеству монстров, которые умрут в $$$i$$$-м раунде.
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
Объяснение для первого примера:
Во время первого раунда происходит следующее:
После первого раунда остаются в живых монстры $$$1$$$ и $$$4$$$.
Во время второго раунда происходит следующее:
В следующих трех раундах остается в живых только монстр $$$4$$$, поэтому ничего не происходит.
Название |
---|