B - Robot Going Back and Forth in a Hallway Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は、長さ L の真っ直ぐな廊下でロボットの動作実験を行っています。この廊下は数直線上の区間 [0, L] に対応しており、両端（座標 0 と座標 L）には壁があります。

廊下には N 台のロボットがあり、i 番目のロボット（1 \leq i \leq N）は時刻 0 において座標 X_i に置かれています。各ロボットには時刻 0 における速度 V_i が設定されています。V_i > 0 のロボットは座標が増加する方向（正の方向）に、V_i < 0 のロボットは座標が減少する方向（負の方向）に、それぞれ速さ |V_i| で等速直線運動を行います。V_i = 0 のロボットは移動せず、その場に留まり続けます。ここで速度の単位は、座標の単位を時間の単位で割ったものです。

ロボットが廊下の端（座標 0 または座標 L）に到達すると、即座に速度の符号が反転し、同じ速さのまま逆方向に移動を続けます。この反射は何度でも繰り返され、ロボットは常に区間 [0, L] 内に留まります。

この反射ルールは時刻 0 においても適用されます。具体的には、初期位置が壁上であるロボットの挙動は以下のとおりです。

  • 座標 0 にいるロボット：V_i < 0 の場合、時刻 0 で即座に速度が反転し、正の方向に速さ |V_i| で移動を開始します。V_i \geq 0 の場合は反転せず、速度 V_i のまま移動します（V_i = 0 ならその場に留まります）。
  • 座標 L にいるロボット：V_i > 0 の場合、時刻 0 で即座に速度が反転し、負の方向に速さ |V_i| で移動を開始します。V_i \leq 0 の場合は反転せず、速度 V_i のまま移動します（V_i = 0 ならその場に留まります）。

各ロボットは独立に運動します。2台以上のロボットが同じ座標に到達しても、互いをすり抜け、それぞれの運動に影響を与えません。

時刻 T における N 台のロボットそれぞれの座標を求めてください。

なお、与えられる入力では、時刻 T における各ロボットの座標は必ず整数となることが保証されます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq 10^9
  • 0 \leq T \leq 10^9
  • 0 \leq X_i \leq L（1 \leq i \leq N）
  • -10^9 \leq V_i \leq 10^9（1 \leq i \leq N）
  • 入力はすべて整数である
  • 時刻 T における各ロボットの座標は必ず整数となる

入力

N L T
X_1 V_1
X_2 V_2
\vdots
X_N V_N
  • 1 行目には、ロボットの台数を表す整数 N、廊下の長さを表す整数 L、求める時刻を表す整数 T が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各ロボットの初期位置と時刻 0 における速度が与えられる。
  • 1 + i 行目（1 \leq i \leq N）では、i 番目のロボットの初期位置 X_i と速度 V_i が、スペース区切りで与えられる。

出力

N 行出力せよ。i 行目（1 \leq i \leq N）には、時刻 T における i 番目のロボットの座標を出力せよ。

入力例 1

3 10 3
2 1
8 3
5 -2

出力例 1

5
3
1

入力例 2

4 6 5
0 -3
6 4
3 0
1 2

出力例 2

3
2
3
1

入力例 3

5 100 7
10 15
50 -30
0 20
99 -1
100 -10

出力例 3

85
40
60
92
30

入力例 4

6 1000000000 1000000000
500000000 0
0 1
1 -1
0 2
500000000 3
999999999 1

出力例 4

500000000
1000000000
999999999
0
500000000
1

入力例 5

1 1 0
0 0

出力例 5

0

Score : 300 pts

Problem Statement

Takahashi is conducting a robot motion experiment in a straight corridor of length L. This corridor corresponds to the interval [0, L] on a number line, and there are walls at both ends (coordinate 0 and coordinate L).

There are N robots in the corridor, and the i-th robot (1 \leq i \leq N) is placed at coordinate X_i at time 0. Each robot has a velocity V_i set at time 0. A robot with V_i > 0 moves at constant speed |V_i| in the direction of increasing coordinates (positive direction), a robot with V_i < 0 moves at constant speed |V_i| in the direction of decreasing coordinates (negative direction), and a robot with V_i = 0 does not move and stays in place. Here, the unit of velocity is the unit of coordinate divided by the unit of time.

When a robot reaches the end of the corridor (coordinate 0 or coordinate L), the sign of its velocity is immediately reversed, and it continues moving in the opposite direction at the same speed. This reflection is repeated any number of times, and the robot always remains within the interval [0, L].

This reflection rule also applies at time 0. Specifically, the behavior of robots whose initial position is on a wall is as follows:

  • A robot at coordinate 0: If V_i < 0, its velocity is immediately reversed at time 0, and it begins moving in the positive direction at speed |V_i|. If V_i \geq 0, it does not reverse and moves with velocity V_i (if V_i = 0, it stays in place).
  • A robot at coordinate L: If V_i > 0, its velocity is immediately reversed at time 0, and it begins moving in the negative direction at speed |V_i|. If V_i \leq 0, it does not reverse and moves with velocity V_i (if V_i = 0, it stays in place).

Each robot moves independently. Even if two or more robots reach the same coordinate, they pass through each other and do not affect each other's motion.

Find the coordinate of each of the N robots at time T.

It is guaranteed that in the given input, the coordinate of each robot at time T is always an integer.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq 10^9
  • 0 \leq T \leq 10^9
  • 0 \leq X_i \leq L (1 \leq i \leq N)
  • -10^9 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • All inputs are integers
  • The coordinate of each robot at time T is always an integer

Input

N L T
X_1 V_1
X_2 V_2
\vdots
X_N V_N
  • The first line contains three space-separated integers: N representing the number of robots, L representing the length of the corridor, and T representing the time to query.
  • From the 2nd line to the (N + 1)-th line, the initial position and velocity at time 0 of each robot are given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the initial position X_i and velocity V_i of the i-th robot, separated by a space.

Output

Output N lines. The i-th line (1 \leq i \leq N) should contain the coordinate of the i-th robot at time T.

Sample Input 1

3 10 3
2 1
8 3
5 -2

Sample Output 1

5
3
1

Sample Input 2

4 6 5
0 -3
6 4
3 0
1 2

Sample Output 2

3
2
3
1

Sample Input 3

5 100 7
10 15
50 -30
0 20
99 -1
100 -10

Sample Output 3

85
40
60
92
30

Sample Input 4

6 1000000000 1000000000
500000000 0
0 1
1 -1
0 2
500000000 3
999999999 1

Sample Output 4

500000000
1000000000
999999999
0
500000000
1

Sample Input 5

1 1 0
0 0

Sample Output 5

0