23521번 - Inelastic Balls 다국어

There is an infinite number line, where the numbers increase from left to right. Some balls roll along the line. Initially, each ball is at an integer point on the line and has unit mass. The sizes of the balls are negligibly small.

The balls start to move continuously at constant velocities: some of them have an initial velocity of $+1$ which means they move $1$ to the right in a unit of time, and others have an initial velocity of $-1$ which means they move $1$ to the left in a unit of time.

When two or more balls meet in the same point at the same moment, a collision happens. The collisions of the balls are perfectly inelastic. It means that all the balls that met are replaced by one new ball. Its mass $m_{\mathrm{new}}$ is equal to the total mass of all the balls that collided, and its velocity can be determined by the momentum conservation principle: the value $v_{\mathrm{new}} \cdot m_{\mathrm{new}}$ after the collision is equal to the sum of values $v_{i} \cdot m_{i}$ of all the balls that collided. The size of the new ball is still negligibly small. Please note: as the balls move continuously, the collision may happen at a non-integer moment.

The number of collisions is finite, so there will be a time when they stop occurring. What are the masses of the balls on the line after all collisions take place? List them from left to right.

The first line of input contains one integer $n$, the number of balls ($1 \le n \le 300\,000$). Each of the next $n$ lines describes one ball in the form "$x$ $v$", where $x$ is the initial coordinate of the ball, and $v$ is its initial velocity. The given coordinates are integers from $0$ to $10^{9}$, inclusive. The velocities are given as either "+1" (moving to the right) or "-1" (moving to the left). All given coordinates are distinct.

Print a line consisting of integers separated by spaces: the masses of the resulting balls after all collisions take place, listed as seen from left to right.