题目描述

有一个周长为 $L$ 的圆。周长上的每个点都有一个坐标值，表示从某个参考点顺时针到达该点的弧长。在这个周长上，有 $N$ 只蚂蚁。这些蚂蚁按照坐标的增加顺序从 $1$ 到 $N$ 编号，第 $i$ 只蚂蚁的坐标为 $X_i$。

这 $N$ 只蚂蚁刚开始行走。对于每只蚂蚁 $i$，你会给出初始方向 $W_i$。如果 $W_i$ 为 $1$，表示第 $i$ 只蚂蚁初始时顺时针行走；如果 $W_i$ 为 $2$，表示第 $i$ 只蚂蚁初始时逆时针行走。每只蚂蚁的行走速度为每秒 $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$ 行应当包含在 $T$ 秒后第 $i$ 只蚂蚁的坐标。这里，每个坐标必须介于 $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