题目描述

训练营科技节上，老师带来了一条“贪吃蛇机器人”。

这条机器人由 N 个小模块连接而成，编号从 1 到 N。编号 1 是头部，编号 N 是尾部。

一开始，机器人安静地排在平面坐标系的 x 轴上：

第 i 个模块的位置是：

(i, 0)

也就是说，初始时头部在 (1, 0)，第 2 个模块在 (2, 0)，一直到尾部在 (N, 0)。

接下来有 Q 条指令，指令分为两种。

指令 1：移动头部

1 C

表示头部向方向 C 移动一步。方向 C 可能是：

• R：向右移动一格；
• L：向左移动一格；
• U：向上移动一格；
• D：向下移动一格。

头部移动后，第 2 个模块会来到第 1 个模块移动前的位置，第 3 个模块会来到第 2 个模块移动前的位置，以此类推。

指令 2：查询位置

2 p

表示询问当前第 p 个模块所在的位置。

请你回答所有查询。

输入格式

第一行输入两个整数 N 和 Q，表示机器人模块数量和指令数量。

接下来 Q 行，每行输入一条指令。

输出格式

对于每条查询指令，输出一行两个整数 x y，表示对应模块当前所在坐标。

样例

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

3 0
2 0
1 1
1 0
1 0

样例说明

样例的移动过程如下图所示：

初始时，5 个模块的位置依次为：

(1,0), (2,0), (3,0), (4,0), (5,0)

所以第一次查询第 3 个模块，输出：

3 0

执行 1 U 后，头部从 (1,0) 移动到 (1,1)，其余模块依次来到前一个模块原来的位置。此时第 3 个模块在 (2,0)，所以第二次查询输出：

2 0

接着执行 1 R 和 1 D 后，头部先到 (2,1)，再到 (2,0)。此时第 3 个模块在 (1,1)，所以第三次查询输出：

1 1

再执行 1 L 后，头部移动到 (1,0)。此时第 1 个模块在 (1,0)，所以第四次查询输出：

1 0

最后查询第 5 个模块，它也在 (1,0)，所以第五次查询输出：

1 0

数据范围

• $1 <= N, Q <= 10^6$
• 保证所有指令合法