CF1852F.Panda Meetups

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 \lt 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 \gt 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.

红熊猫们来到小镇与它们的亲戚——蓝熊猫们会面！小镇被建模为一条数轴。

熊猫们已经规划好了会面，但日程却不断变化。你将收到 $q$ 个更新，每个更新形如 x t c：

• 若 $c \lt 0$，表示在位置 $x$、时刻 $t$ 新增了 $|c|$ 只红熊猫进入数轴。此后，每单位时间，每只红熊猫可独立地在数轴上向左或向右移动一个单位，或保持不动。
• 若 $c \gt 0$，表示在时刻 $t$ 有 $c$ 只蓝熊猫前往位置 $x$ 寻找红熊猫。若某只蓝熊猫在该特定位置与时刻未遇到任何红熊猫，则它会沮丧地立即离开数轴；若在该位置与时刻恰有红熊猫存在，则二者结为朋友并一同离开数轴。每只红熊猫最多与一只蓝熊猫结为朋友，反之亦然。

所有更新按 $x$ 值非递减顺序给出。在每次更新后，请输出：基于输入中截至（含）当前更新的所有更新信息，在红熊猫采取最优移动策略的前提下，所能达成的最大友谊对数。

红熊猫在不同更新之间的移动策略可以不同。

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 \lt |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.

第一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$），表示更新操作的次数。

接下来的 $q$ 行中，第 $i$ 行包含三个整数 $x_i$、$t_i$ 和 $c_i$（$0 \leq x_i \leq 10^9$，$0 \leq t_i \leq 10^9$，$0 \lt |c_i| \leq 1000$），描述第 $i$ 次更新操作。

保证输入的 $x_i$ 是以非递减顺序给出的。

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

每次更新后，输出最多可以建立的友谊数量。

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.

在第一个样例中，每次更新后友谊的数量可按如下方式优化：

1. 此时有 $3$ 只蓝熊猫，在时刻 $6$、位置 $0$ 处寻找红熊猫。此时任意位置均无红熊猫，因此不存在友谊。
2. 此时有 $5$ 只红熊猫在时刻 $2$、位置 $4$ 处出现。其中 $4$ 只红熊猫可于时刻 $6$ 到达位置 $0$，并与已有的 $3$ 只蓝熊猫中的 $3$ 只建立友谊。
3. 此时有 $6$ 只红熊猫在时刻 $4$、位置 $7$ 处出现。此步未新增蓝熊猫，因此友谊的最大数量仍为 $3$。
4. 此时有 $100$ 只蓝熊猫在时刻 $5$、位置 $10$ 处出现。此时无红熊猫能在时刻 $5$ 到达该位置，因此未产生新的友谊。
5. 此时有 $7$ 只蓝熊猫在时刻 $8$、位置 $10$ 处出现。位于时刻 $4$、位置 $7$ 的 $6$ 只红熊猫，以及位于时刻 $2$、位置 $4$ 的 $1$ 只红熊猫，均可于时刻 $8$ 到达位置 $10$，并与该处的 $7$ 只蓝熊猫全部建立友谊，从而新增 $7$ 对友谊。此时友谊总数达到 $10$ 对。