Красные панды приехали в город, чтобы встретиться со своими родственниками, синими пандами! Город представлен в виде числовой оси.
Панды уже запланировали свою встречу, но график постоянно меняется. Вам дано \(q\) обновлений вида x t c.
Запросы представлены в порядке неубывания значений \(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
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач