310567: CF1852F. Panda Meetups

F. Panda Meetupstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

The red pandas are in town to meet their relatives, the blue pandas! The town is modeled by a number line.

The pandas have already planned their meetup, but the schedule keeps changing. You are given $q$ updates of the form x t c.

• If $c < 0$, it means $|c|$ more red pandas enter the number line at position $x$ and time $t$. Then, each unit of time, they can each independently move one unit in either direction across the number line, or not move at all.
• If $c > 0$, it means that $c$ more blue pandas check position $x$ for red pandas at time $t$. If a blue panda does not meet a red panda at that specific location and time, they dejectedly leave the number line right away. If there is a red panda at a position at the same time a blue panda checks it, they form a friendship and leave the number line. Each red panda can form a friendship with at most one blue panda and vice versa.

The updates will be given in order of non-decreasing $x$ values. After each update, please print the maximum number of friendships if the red pandas move in an optimal order based on all the updates given in the input above (and including) this update.

The order in which a red panda moves can change between updates.

Input

The first line contains $q$ ($1 \leq q \leq 2 \cdot 10^5$)  – the number of updates.

The $i$-th line of the next $q$ lines consists of $3$ integers $x_i$, $t_i$ and $c_i$ ($0 \leq x_i \leq 10^9$, $0 \leq t_i \leq 10^9$, $0 < |c_i| \leq 1000$) – the description of the $i$-th update.

It is guaranteed that the $x_i$ will be given in non-decreasing order.

Output

After each update, print the maximum number of friendships that can be formed.

ExamplesInput

5
0 6 3
4 2 -5
7 4 -6
10 5 100
10 8 7

Output

0
3
3
3
10

Input

5
0 6 3
4 2 -5
7 4 -6
10 5 100
11 8 7

Output

0
3
3
3
9

Input

7
0 8 6
2 7 -2
3 1 -6
5 3 -8
7 3 -3
8 0 -2
8 2 1

Output

0
0
6
6
6
6
7

Input

4
0 0 -3
0 0 2
0 0 4
0 0 -10

Output

0
2
3
6

Note

In the first example, the number of friendships after each update can be optimized as follows:

1. $3$ blue pandas now check for red pandas at position $0$ at time $6$. There are no red pandas anywhere, so there are no friendships.
2. $5$ red pandas now appear at position $4$ and time $2$. $4$ of the red pandas can travel to position $0$ at time $6$, where $3$ of them can make friendships with the $3$ existing blue pandas.
3. $6$ red pandas now appear at position $7$ and time $4$. No new blue pandas are added, so the maximum number of friendships is still $3$.
4. $100$ blue pandas now appear at position $10$ and time $5$. No red pandas can reach them at a time of $5$, so no new friendships are created.
5. $7$ blue pandas now appear at position $10$ and time $8$. $6$ of the red pandas at position $7$ and time $4$, along with $1$ red panda at position $4$ and time $2$, can reach $7$ of the blue pandas at position $10$ at time $8$, adding $7$ new friendships. This brings the total to $10$ friendships.

题目大意：
题目描述了一个关于红熊猫和蓝熊猫相遇的问题。在一个用数轴表示的小镇上，红熊猫和蓝熊猫计划相遇。给出一系列的更新，格式为 x t c，表示在时间 t，位置 x 发生的事件：

- 如果 c < 0，表示有 |c| 个红熊猫在时间 t 进入数轴的位置 x。红熊猫每单位时间可以选择向左或向右移动一个单位，或者不移动。
- 如果 c > 0，表示有 c 个蓝熊猫在时间 t 检查位置 x 是否有红熊猫。如果蓝熊猫在特定位置和时间没有遇到红熊猫，它们会立即离开数轴。如果蓝熊猫在某个位置和时间遇到红熊猫，它们会形成友谊并离开数轴。每个红熊猫最多与一个蓝熊猫形成友谊，反之亦然。

更新按照 x 的非递减顺序给出。在每次更新后，请输出如果红熊猫根据以上所有更新（包括此次更新）以最优顺序移动时，可以形成的最大友谊数量。红熊猫的移动顺序可以在更新之间改变。

输入输出数据格式：
输入：
- 第一行包含一个整数 q (1 ≤ q ≤ 2 * 10^5)，表示更新的数量。
- 接下来的 q 行，每行包含 3 个整数 x_i, t_i 和 c_i (0 ≤ x_i ≤ 10^9, 0 ≤ t_i ≤ 10^9, 0 < |c_i| ≤ 1000)，描述第 i 个更新。
- 保证 x_i 按非递减顺序给出。

输出：
- 对于每个更新，输出在此次更新后可以形成的最大友谊数量。

示例输入输出见原题目描述。题目大意： 题目描述了一个关于红熊猫和蓝熊猫相遇的问题。在一个用数轴表示的小镇上，红熊猫和蓝熊猫计划相遇。给出一系列的更新，格式为 x t c，表示在时间 t，位置 x 发生的事件： - 如果 c < 0，表示有 |c| 个红熊猫在时间 t 进入数轴的位置 x。红熊猫每单位时间可以选择向左或向右移动一个单位，或者不移动。 - 如果 c > 0，表示有 c 个蓝熊猫在时间 t 检查位置 x 是否有红熊猫。如果蓝熊猫在特定位置和时间没有遇到红熊猫，它们会立即离开数轴。如果蓝熊猫在某个位置和时间遇到红熊猫，它们会形成友谊并离开数轴。每个红熊猫最多与一个蓝熊猫形成友谊，反之亦然。 更新按照 x 的非递减顺序给出。在每次更新后，请输出如果红熊猫根据以上所有更新（包括此次更新）以最优顺序移动时，可以形成的最大友谊数量。红熊猫的移动顺序可以在更新之间改变。 输入输出数据格式： 输入： - 第一行包含一个整数 q (1 ≤ q ≤ 2 * 10^5)，表示更新的数量。 - 接下来的 q 行，每行包含 3 个整数 x_i, t_i 和 c_i (0 ≤ x_i ≤ 10^9, 0 ≤ t_i ≤ 10^9, 0 < |c_i| ≤ 1000)，描述第 i 个更新。 - 保证 x_i 按非递减顺序给出。 输出： - 对于每个更新，输出在此次更新后可以形成的最大友谊数量。 示例输入输出见原题目描述。