D. Безумные монстры
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру (опять). Угадайте, что он делает? Правильно, убивает монстров.

В ряд стоят $$$n$$$ монстров, пронумерованных от $$$1$$$ до $$$n$$$. У $$$i$$$-го монстра есть два параметра: значение атаки, равное $$$a_i$$$, и значение защиты, равное $$$d_i$$$. Чтобы убить этих монстров, Монокарп наложил на них заклинание безумия, так что они атакуют друг друга, а не персонажа Монокарпа.

Бой состоит из $$$n$$$ раундов. В каждом раунде происходит следующее:

  • сначала каждый живой монстр $$$i$$$ наносит $$$a_i$$$ урона ближайшему живому монстру слева (если он существует) и ближайшему живому монстру справа (если он существует);
  • затем каждый живой монстр $$$j$$$, который получил больше $$$d_j$$$ урона в течение этого раунда, умирает. Т.е. $$$j$$$-й монстр умирает тогда и только тогда, когда его значение защиты $$$d_j$$$ строго меньше суммарного урона, который он получил в этом раунде.

Для каждого раунда вычислите количество монстров, которые умрут во время этого раунда.

Входные данные

Первая строка содержит одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите $$$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$$$ наносит $$$3$$$ урона монстру $$$2$$$;
  • монстр $$$2$$$ наносит $$$4$$$ урона монстру $$$1$$$ и монстру $$$3$$$;
  • монстр $$$3$$$ наносит $$$7$$$ урона монстру $$$2$$$ и монстру $$$4$$$;
  • монстр $$$4$$$ наносит $$$5$$$ урона монстру $$$3$$$ и монстру $$$5$$$;
  • монстр $$$5$$$ наносит $$$10$$$ урона монстру $$$4$$$;
  • монстр $$$1$$$ не умирает, так как он получил $$$4$$$ урона и его защита равна $$$4$$$;
  • монстр $$$2$$$ умирает, так как он получил $$$10$$$ урона и его защита равна $$$9$$$;
  • монстр $$$3$$$ умирает, так как он получил $$$9$$$ урона и его защита равна $$$1$$$;
  • монстр $$$4$$$ не умирает, так как он получил $$$17$$$ урона и его защита равна $$$18$$$;
  • монстр $$$5$$$ умирает, так как он получил $$$5$$$ урона и его защита равна $$$1$$$.

После первого раунда остаются в живых монстры $$$1$$$ и $$$4$$$.

Во время второго раунда происходит следующее:

  • монстр $$$1$$$ наносит $$$3$$$ урона монстру $$$4$$$;
  • монстр $$$4$$$ наносит $$$5$$$ урона монстру $$$1$$$;
  • монстр $$$1$$$ умирает, так как он получил $$$5$$$ урона и его защита равна $$$4$$$;
  • монстр $$$4$$$ не умирает, так как он получил $$$3$$$ урона и его защита равна $$$18$$$.

В следующих трех раундах остается в живых только монстр $$$4$$$, поэтому ничего не происходит.