题目描述

高桥制作了一款游戏，玩家将在坐标平面上控制一条龙。

这条龙由编号为 1 到 N 的 N 个部分组成，其中第 1 部分称为头部。

初始时，第 i 部分位于坐标 $(i, 0)$。处理 Q 次询问，具体如下：

1. 1 C：将头部向方向 C 移动 1 单位。其中 C 是 R、L、U、D 之一，分别代表 x 轴正方向、x 轴负方向、y 轴正方向、y 轴负方向。除头部外的每个部分都会跟随其前方的部分移动。即，第 i 部分（$2 \le i \le N$）会移动到第 $i-1$ 部分移动前所在的坐标。

2. 2 p：查询第 p 部分的坐标。

输入格式

输入从标准输入给出，格式如下：

• $N$ $Q$
• $query_1$

⋮

• $query_Q$

每个询问为以下两种格式之一：

• $1$ $C$
• $2$ $p$

输出格式

输出 q 行，其中 q 是第二种类型询问的数量。

第 i 行包含用空格分隔的 x 和 y，$(x, y)$ 为第 i 次该类型询问的答案。

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

在每次处理第二种类型的询问时，各部分的位置如下：

（图示：龙的各部分在移动过程中的位置变化） 请注意，多个部分可能位于同一坐标。

数据规模与约定

• $2 \le N < 10^6$
• $1 \le Q \le 2 \times 10^5$
• 对于第一种类型的询问，C 是 R、L、U、D 之一。
• 对于第二种类型的询问，$1 \le p \le N$。
• 所有输入的数值均为整数。