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