G - ロボット Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

Problem Statement

すぬけ君は N 個のロボットを持っている。最初に、i 番目のロボットは座標 (x_i, y_i) に向き d_i の方向を向いて止まっている。 d_i は U, D, L, R のいずれかであり、それぞれ y 座標の正の方向、 y 座標の負の方向、 x 座標の負の方向、 x 座標の正の方向を表す。

このロボットは、何か (すぬけ君または他のロボット) に触れると向いている方向に毎秒 1 の速さで動き出す性質がある。また、このロボットはすり抜けることができるので、動いているロボットが他のロボットに衝突しても止まったり運動の向きや速さが変わることはない。

すぬけ君は、時刻 0 にロボット 1 をさわった。時刻 T のそれぞれのロボットの座標を求めよ。

Constraints

  • 1 ≤ N ≤ 100000
  • 0 ≤ T ≤ 10^{18}
  • 0 ≤ x_i, y_i ≤ 10^9
  • d_i は U, D, L, R のいずれかである
  • 時刻 0 にはどの二つのロボットも同じ場所にない

Input Format

入力は以下の形式で標準入力から与えられる。 
N T
x_1 y_1 d_1
:
x_N y_N d_N

Output Format

N 行出力せよ。i 行目には、i 番目の点の座標を空白で区切って出力せよ。

Sample Input 1

5 10
1 0 U
3 1 U
1 2 R
1 1 L
0 1 R

Sample Output 1

1 10
3 6
9 2
-8 1
8 1