F. Встречи панд
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Красные панды приехали в город, чтобы встретиться со своими родственниками, синими пандами! Город представлен в виде числовой оси.

Панды уже запланировали свою встречу, но график постоянно меняется. Вам дано $$$q$$$ обновлений вида x t c.

  • Если $$$c < 0$$$, это означает, что дополнительно $$$|c|$$$ красных панд входят на числовую ось в позиции $$$x$$$ и времени $$$t$$$. Затем каждую секунду они могут независимо перемещаться на одну единицу в любом направлении по числовой оси или не перемещаться вовсе.
  • Если $$$c > 0$$$, это означает, что дополнительно $$$c$$$ синих панд проверяют позицию $$$x$$$ на наличие красных панд в момент времени $$$t$$$. Если синяя панда не встречает красную панду в этом конкретном месте и времени, она сразу печально покидает числовую ось. Если красная панда есть на позиции в то время, когда синяя панда ее проверяет, они становятся друзьями и покидают числовую ось. Каждая красная панда может стать другом не более чем одной синей панды и наоборот.

Запросы представлены в порядке неубывания значений $$$x$$$. После каждого запроса выведите максимальное количество пар друзей, которое может быть сформировано, если красные панды движутся в оптимальном порядке на основе всех событий, представленных во входных данных до этого обновления (включительно).

Движения красных панд могут меняться от обновления к обновлению.

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

Первая строка содержит $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — количество обновлений.

$$$i$$$-я строка из следующих $$$q$$$ строк содержит $$$3$$$ целых числа $$$x_i$$$, $$$t_i$$$ и $$$c_i$$$ ($$$0 \leq x_i \leq 10^9$$$, $$$0 \leq t_i \leq 10^9$$$, $$$0 < |c_i| \leq 1000$$$) — описание $$$i$$$-го обновления.

Гарантируется, что $$$x_i$$$ будут представлены в порядке неубывания.

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

После каждого обновления выведите максимальное количество пар друзей, которое может быть сформировано.

Примеры
Входные данные
5
0 6 3
4 2 -5
7 4 -6
10 5 100
10 8 7
Выходные данные
0
3
3
3
10
Входные данные
5
0 6 3
4 2 -5
7 4 -6
10 5 100
11 8 7
Выходные данные
0
3
3
3
9
Входные данные
7
0 8 6
2 7 -2
3 1 -6
5 3 -8
7 3 -3
8 0 -2
8 2 1
Выходные данные
0
0
6
6
6
6
7
Входные данные
4
0 0 -3
0 0 2
0 0 4
0 0 -10
Выходные данные
0
2
3
6
Примечание

В первом примере количество пар друзей после каждого обновления может быть оптимизировано следующим образом:

  1. $$$3$$$ синих панды проверяют наличие красных панд на позиции $$$0$$$ в момент времени $$$6$$$. Нигде нет красных панд, поэтому пар друзей не возникает.
  2. $$$5$$$ красных панд появляются на позиции $$$4$$$ в момент времени $$$2$$$. $$$4$$$ из них могут переместиться на позицию $$$0$$$ в момент времени $$$6$$$, где $$$3$$$ из них могут стать друзьями с $$$3$$$ существующими синими пандами.
  3. $$$6$$$ красных панд появляются на позиции $$$7$$$ в момент времени $$$4$$$. Новые синие панды не добавляются, поэтому максимальное количество пар друзей остается $$$3$$$.
  4. $$$100$$$ синих панд появляются на позиции $$$10$$$ в момент времени $$$5$$$. Ни одна красная панда не может достичь их в момент времени $$$5$$$, поэтому новых пар друзей не создается.
  5. $$$7$$$ синих панд появляются на позиции $$$10$$$ в момент времени $$$8$$$. $$$6$$$ красных панд на позиции $$$7$$$ в момент времени $$$4$$$, вместе с $$$1$$$ красной пандой на позиции $$$4$$$ в момент времени $$$2$$$, могут достичь $$$7$$$ синих панд на позиции $$$10$$$ в момент времени $$$8$$$, добавляя $$$7$$$ новых пар друзей. Это приводит к общему количеству пар друзей, равному $$$10$$$.