题目描述

周の長さ $L$ の円があります。 この円の周上には座標が設定されていて、座標の値は、ある基準点からどれだけ時計回りに進んだかを表しています。

この円周上に $N$ 匹の蟻がいます。 蟻には、座標の小さいものから順に、$1$ から $N$ までの番号がついています。 $i$ 番目の蟻は座標 $X_i$ にいます。

これから、$N$ 匹の蟻は一斉に動き出します。 $i$ 匹目の蟻は、$W_i$ が $1$ なら時計回りに、$W_i$ が $2$ なら反時計回りに動き始めます。 全ての蟻の移動速度は常に、$1$ 秒間にちょうど $1$ の距離を進む速さです。 蟻が動いていくと、二つの蟻がぶつかることがあります。 その時はどちらの蟻も、ぶつかった瞬間に進む向きを反転して動き続けます。

蟻が動き始めてから $T$ 秒後にそれぞれの蟻がいる位置を求めて下さい。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $L$ $T$ $X_1$ $W_1$ $X_2$ $W_2$ $:$ $X_N$ $W_N$

输出格式

出力は $N$ 行からなる。 出力の $i$ 行目には、$i$ 番目の蟻が $T$ 秒後にいる位置の座標を出力せよ。 なお、座標の値は $0$ 以上 $L$ 未満の値として出力せよ。

题目大意

有一个长度为 $L$ 的圆环，上面有 $N$ 个蚂蚁，位置分别为 $x_i$，运动方向为 $d_i$，$1$ 表示顺时针，$2$ 表示逆时针。

每只蚂蚁将会同时开始以单位速度运动，如果两只蚂蚁相遇, 那么它们会改变自己的方向继续运动。

求 $T$ 秒之后每只蚂蚁的位置。

3 8 3
0 1
3 2
6 1

1
3
0

4 20 9
7 2
9 1
12 1
18 1

7
18
18
1

提示

制約

• 入力は全て整数である
• $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$

Sample Explanation 1

蟻が動き始めてから $1.5$ 秒後、蟻 $1$ と 蟻 $2$ が、座標 $1.5$ の位置でぶつかります。 その $1$ 秒後、蟻 $1$ と蟻 $3$ が、座標 $0.5$ の位置ぶつかります。 その $0.5$ 秒後、つまり蟻が動き始めてから $3$ 秒後には、 蟻 $1$ 、$2$ 、$3$ はそれぞれ座標 $1$ 、$3$ 、$0$ にいます。