問題文

周の長さ $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$ 未満の値として出力せよ。

入力例 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