← 返回题目列表

AtCoder · agc013_c

C. 圆圈上的蚂蚁

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

有一个周长为 L。 圆周上的每个点都有一个坐标值,它表示从某个参考点顺时针到该点的弧长。 在这个圆周上,有 N 蚂蚁。 这些蚂蚁有编号 1 通过 N 按坐标递增的顺序,并且 ant i 位于坐标处 X_i.

的 N 蚂蚁刚刚开始行走。 对于每只蚂蚁 i,给你初始方向 W_i。蚂蚁 i 最初是顺时针行走,如果 W_i is 1;逆时针如果 W_i is 2。 每只蚂蚁都以恒定的速度行走 1 每秒。 有时,两只蚂蚁会互相碰撞。 然后,这两只蚂蚁都会转身并开始朝相反的方向行走。

对于每只蚂蚁,找到它之后的位置 T 秒。

约束

  • 所有输入值均为整数。
  • 1 \leq N \leq 10^5
  • 1 \leq L \leq 10^9
  • 1 \leq T \leq 10^9
  • 0 \leq X_1 < X_2 < ... < X_N \leq L - 1
  • 1 \leq W_i \leq 2

输入

输入由标准输入按以下格式给出:

N L T
X_1 W_1
X_2 W_2
:
X_N W_N

输出

打印 N 行。 的 i第行应包含 ant 的坐标 i 之后 T 秒。这里,每个坐标必须在 0 和 L-1,包括在内。


示例输入 1

3 8 3
0 1
3 2
6 1

示例输出 1

1
3
0

1.5 蚂蚁开始行走后几秒,蚂蚁 1 和 2 在坐标处碰撞 1.5. 1 第二次之后,蚂蚁 1 和 3 在坐标处碰撞 0.5. 0.5 秒后,即 3 蚂蚁开始行走后几秒,蚂蚁 1, 2 和 3 位于坐标处 1, 3 和 0。


示例输入 2

4 20 9
7 2
9 1
12 1
18 1

示例输出 2

7
18
18
1