配点 : $700$ 点

問題文

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

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

これから、$N$ 匹の蟻は一斉に動き出します。 $i$ 匹目の蟻は、$W_i$ が $1$ なら時計回りに、$W_i$ が $2$ なら反時計回りに動き始めます。 全ての蟻の移動速度は常に、$1$ 秒間にちょうど $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$ 行目には、$i$ 番目の蟻が $T$ 秒後にいる位置の座標を出力せよ。 なお、座標の値は $0$ 以上 $L$ 未満の値として出力せよ。

3 8 3
0 1
3 2
6 1

1
3
0

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

4 20 9
7 2
9 1
12 1
18 1

7
18
18
1