Монокарп играет в компьютерную игру (опять). Угадайте, что он делает? Правильно, убивает монстров.
В ряд стоят \(n\) монстров, пронумерованных от \(1\) до \(n\). У \(i\)-го монстра есть два параметра: значение атаки, равное \(a_i\), и значение защиты, равное \(d_i\). Чтобы убить этих монстров, Монокарп наложил на них заклинание безумия, так что они атакуют друг друга, а не персонажа Монокарпа.
Бой состоит из \(n\) раундов. В каждом раунде происходит следующее:
- сначала каждый живой монстр \(i\) наносит \(a_i\) урона ближайшему живому монстру слева (если он существует) и ближайшему живому монстру справа (если он существует);
- затем каждый живой монстр \(j\), который получил больше \(d_j\) урона в течение этого раунда, умирает. Т.е. \(j\)-й монстр умирает тогда и только тогда, когда его значение защиты \(d_j\) строго меньше суммарного урона, который он получил в этом раунде.
Для каждого раунда вычислите количество монстров, которые умрут во время этого раунда.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел. \(i\)-е целое число должно быть равно количеству монстров, которые умрут в \(i\)-м раунде.
Примечание
Объяснение для первого примера:
Во время первого раунда происходит следующее:
- монстр \(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\), поэтому ничего не происходит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|