[AGC013C] Ants on a Circle

有一个长度为 $L$ 的圆环，上面有 $N$ 个蚂蚁，位置分别为 $x_i$，运动方向为 $d_i$，$1$ 表示顺时针，$2$ 表示逆时针。 每只蚂蚁将会同时开始以单位速度运动，如果两只蚂蚁相遇, 那么它们会改变自己的方向继续运动。 求 $T$ 秒之后每只蚂蚁的位置。

[problemUrl]: https://atcoder.jp/contests/agc013/tasks/agc013_c 周の長さ $ 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 $ 未満の値として出力せよ。

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 $ にいます。