Красные панды приехали в город, чтобы встретиться со своими родственниками, синими пандами! Город представлен в виде числовой оси.
Панды уже запланировали свою встречу, но график постоянно меняется. Вам дано $$$q$$$ обновлений вида x t c.
- Если $$$c < 0$$$, это означает, что дополнительно $$$|c|$$$ красных панд входят на числовую ось в позиции $$$x$$$ и времени $$$t$$$. Затем каждую секунду они могут независимо перемещаться на одну единицу в любом направлении по числовой оси или не перемещаться вовсе.
- Если $$$c > 0$$$, это означает, что дополнительно $$$c$$$ синих панд проверяют позицию $$$x$$$ на наличие красных панд в момент времени $$$t$$$. Если синяя панда не встречает красную панду в этом конкретном месте и времени, она сразу печально покидает числовую ось. Если красная панда есть на позиции в то время, когда синяя панда ее проверяет, они становятся друзьями и покидают числовую ось. Каждая красная панда может стать другом не более чем одной синей панды и наоборот.
Запросы представлены в порядке неубывания значений $$$x$$$. После каждого запроса выведите максимальное количество пар друзей, которое может быть сформировано, если красные панды движутся в оптимальном порядке на основе всех событий, представленных во входных данных до этого обновления (включительно).
Движения красных панд могут меняться от обновления к обновлению.
Выходные данные
После каждого обновления выведите максимальное количество пар друзей, которое может быть сформировано.
Примеры
Выходные данные
0
3
3
3
10
Выходные данные
0
3
3
3
9
Выходные данные
0
0
6
6
6
6
7
Примечание
В первом примере количество пар друзей после каждого обновления может быть оптимизировано следующим образом:
- $$$3$$$ синих панды проверяют наличие красных панд на позиции $$$0$$$ в момент времени $$$6$$$. Нигде нет красных панд, поэтому пар друзей не возникает.
- $$$5$$$ красных панд появляются на позиции $$$4$$$ в момент времени $$$2$$$. $$$4$$$ из них могут переместиться на позицию $$$0$$$ в момент времени $$$6$$$, где $$$3$$$ из них могут стать друзьями с $$$3$$$ существующими синими пандами.
- $$$6$$$ красных панд появляются на позиции $$$7$$$ в момент времени $$$4$$$. Новые синие панды не добавляются, поэтому максимальное количество пар друзей остается $$$3$$$.
- $$$100$$$ синих панд появляются на позиции $$$10$$$ в момент времени $$$5$$$. Ни одна красная панда не может достичь их в момент времени $$$5$$$, поэтому новых пар друзей не создается.
- $$$7$$$ синих панд появляются на позиции $$$10$$$ в момент времени $$$8$$$. $$$6$$$ красных панд на позиции $$$7$$$ в момент времени $$$4$$$, вместе с $$$1$$$ красной пандой на позиции $$$4$$$ в момент времени $$$2$$$, могут достичь $$$7$$$ синих панд на позиции $$$10$$$ в момент времени $$$8$$$, добавляя $$$7$$$ новых пар друзей. Это приводит к общему количеству пар друзей, равному $$$10$$$.