题目描述

小高创建了一个游戏，玩家在坐标平面上控制上控制一条龙。龙由 $N$ 个部分组成，编号从 $1$ 到 $N$，其中第 $1$ 部分被称为 "头"。初始时，第 $i$ 个部位位于坐标 $（i , 0）$。按以下方式处理 $Q$ 个查询：

1. 1 C：将头部向 $C$ 方向移动 $1$ 个单位。这里，$C$ 是 R、L、U 和 D 之一，分别表示 $x$ 轴正方向、$x$ 轴负方向、$y$ 轴正方向和 $y$ 轴负方向。除头部外的每个部分都会跟随前面的部分移动。也就是说，第 $i$ 部分 $(2≤i≤N)$ 会移动到第 $i−1$ 部分移动前所在的坐标。
2. 2 p：查询第 $p$ 部分的坐标。

输入格式

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

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

输出格式

输出 $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

提示

样例 1 解释

在处理第二种查询时，各部分的位置如下：

注意，多个部分可能存在于同一坐标。

数据范围

• $2\ \leq\ N\ \leq\ 10^6$
• $1\ \leq\ Q\ \leq\ 2\times\ 10^5$
• 在第一种类型的查询中，C 是 R、L、U 或 D 中的任意一个。
• 在第二种类型的询问中$1\leq\ p\ \leq\ N$
• 输入中包含的所有数值均为整数。