410664: GYM104072 B Balls

For the sake of having a problem statement, Bob has a large collection of $$$N$$$($$$1 \leq N \leq 10^5$$$) balls of radius $$$R$$$ $$$(1 \leq R \leq 10)$$$. He wants to roll them from one side of a table to the other. You might imagine the table as an 1D axis of infinite length.

A ball will roll from a given position $$$p_i$$$ ($$$0 \leq p_i \leq 10^9)$$$ with a non-zero speed $$$s_i (-10^9 \leq s_i \leq 10^9)$$$ to the left (negative speeds) or to the right (positive speeds) edge of the table, without ever falling down (the table is magical and has infinite length!). All balls start rolling at the same point in time, 0.

Now, Bob is wondering: given these balls, and the fact that they move from left to right or from right to left, what is their position during a moment in time, $$$T$$$ $$$(0 \leq T \leq 10^9)$$$? Of course, you can consider that the collision between two balls happens instantly, without friction, hence, after a collision, the balls simply swap their speeds.

The first line of input contains three integers: N($$$1 \leq N \leq 10^5$$$), R($$$1 \leq R \leq 10$$$), T($$$0\leq T \leq 10^9$$$), representing the number of balls, the radius they have and the moment in time during which you must know where the balls are.

$$$N$$$ more lines will follow. Line $$$i$$$ will contain two positive integers, $$$p_i$$$($$$0 \leq p_i \leq 10^9$$$) and $$$s_i$$$($$$0 < |s_i| \leq 10^9$$$), denoting the initial position and the speed of ball $$$i$$$. If a ball rolls to the left, its speed will be $$$s_i$$$, where $$$-10^9 \leq s_i \leq -1$$$. Similarly, if a ball rolls to the right, its speed will be $$$s_i$$$, with $$$1 \leq s_i \leq 10^9$$$. It is guaranteed that initially the balls do not overlap, but they can touch each other.

On a line, print $$$N$$$ values $$$p_i$$$ representing the position of all balls at moment of time $$$T$$$. Note that the positions should be printed in a non-decreasing order.

3 1 5
3 -1
8 -2
1 3

-6 -2 20