题目描述

Takahashi 创造了一款游戏，游戏中玩家可以在坐标平面上控制一条“龙”。

一条“龙”包含 $N$ 个编号为 $1$ 到 $N$ 的部位，而部位 $1$ 被叫做“头”。

初始状态下，第 $i$ 个部位位于坐标（$i$ , $0$）。下面你需要回答 $Q$ 个询问。

• 1 C：向方向 $C$ 将编号为 $1$ 的头移动一个单位长度。$C$ 可能是 R、L、U、D 中的一个字母，分别代表 $x$ 轴正方向、$x$ 轴负方向、$y$ 轴正方向、$y$ 轴负方向。其他的所有部位都会跟随上一个部位移动。形式化地，编号为 $i$ 的部位会移动到编号为 $i-1$ 的部位先前所在的位置。
• 2 p：输出部位 $p$ 的坐标。

你需要对所有询问 2 做出回答。

输入格式

第一行两个整数 $N$、$Q$。

下面 $Q$ 行，格式如题面所示。

输出格式

对于每个询问 2 p，输出部位 $p$ 当前的坐标。

样例 #1

样例输入 #1

5 9
2 3
1 U
2 3
1 R
1 D
2 3
1 L
2 1
2 5

样例输出 #1

3 0
2 0
1 1
1 0
1 0

提示

制約

• $2\ \leq\ N\ \leq\ 10^6$
• $1\ \leq\ Q\ \leq\ 2\times\ 10^5$