分数: 300 分
问题陈述
高桥正在一条长长的笔直走廊里进行机器人运动实验 L。该走廊对应区间 [0, L] 在一条数轴上,两端都有墙(坐标 0 和坐标 L).
有 N 走廊里的机器人,以及 i第机器人(1 \leq i \leq N) 放置在坐标处 X_i 时间 0。每个机器人都有一个速度 V_i 设置时间 0。一个机器人 V_i > 0 匀速移动 |V_i| 在增加坐标的方向(正方向)上,机器人 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,它保持在原位)。
每个机器人独立移动。即使两个或多个机器人到达同一坐标,它们也会相互穿过,不会影响彼此的运动。
找到每个的坐标 N 机器人当时 T.
保证在给定的输入中,每个机器人在某个时刻的坐标 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
- 第一行包含三个空格分隔的整数: N 代表机器人数量, L 代表走廊的长度,以及 T 代表查询的时间。
- 从第 2 行到 (N + 1)第行,此时的初始位置和速度 给出了每个机器人的 0 。
- 的 (1 + i)- 第行 (1 \leq i \leq N) 包含初始位置 X_i 和速度 V_i 的 i第一个机器人,以空格分隔。
输出
输出 N 行。的 i- 第行 (1 \leq i \leq N)应包含的坐标 i当时第个机器人 T.
示例输入 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