Snuke 有 $N$ 个机器人，编号为 $1$ 到 $N$。初始时，第 $i$ 个机器人位于 $(x_i, y_i)$，其初始朝向为 $d_i$。其中 $d_i$ 为 'U'、'D'、'L'、'R' 中的一个，分别代表 $y$ 轴正方向、$y$ 轴负方向、$x$ 轴负方向和 $x$ 轴正方向。机器人和 Snuke 在平面上被视为点。

初始时，所有机器人均处于静止状态。然而，当一个机器人被某物（Snuke 或另一个机器人）触碰时，它会立即以单位速度沿其朝向开始移动。这些机器人由奇异材料制成，它们可以穿过其他机器人。一旦机器人开始移动，无论发生什么，它都会保持移动；即使它触碰了另一个机器人，也不会改变其方向和速度。

Snuke 在时间 $0$ 触碰了机器人 $1$。请计算每个机器人在时间 $T$ 的坐标。

输入格式

第一行包含两个整数 $N$ 和 $T$ ($1 \le N \le 10^5, 0 \le T \le 10^{18}$)。 接下来的 $N$ 行中，第 $i$ 行包含两个整数 $x_i, y_i$ 和一个字符 $d_i$，表示第 $i$ 个机器人的初始坐标和朝向 ($0 \le x_i, y_i \le 10^9$, $d_i$ 为 'U', 'D', 'L', 'R' 中的一个)。 在时间 $0$ 时，没有两个机器人处于相同位置。

输出格式

输出 $N$ 行。第 $i$ 行输出第 $i$ 个机器人在时间 $T$ 的坐标。

样例

样例输入 1

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

样例输出 1

1 10
3 6
9 2
-8 1
8 1