Codeforces Round 887 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dp

flows

*3500

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Panda Meetups

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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.

Examples

Input

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:

- $$$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.
- $$$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.
- $$$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$$$.
- $$$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.
- $$$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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/28/2024 23:13:46 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|