龙之追踪

题目描述

高桥君制作了一个在坐标平面上操作龙的游戏。

龙由编号 $1$ 到 $N$ 的 $N$ 个部件组成,其中部件 $1$ 称为头部。

初始时,部件 $i$ 位于坐标 $(i,0)$。请处理 $Q$ 个如下查询。

• 1 C: 将头部沿方向 $C$ 移动 $1$。这里,$C$ 是 R、L、U、D 之一,分别表示 $x$ 轴正方向、$x$ 轴负方向、$y$ 轴正方向、$y$ 轴负方向。头部以外的所有部件都跟随其前一个部件移动。即,部件 $i\ (2 \leq i \leq N)$ 移动到移动前部件 $i-1$ 所在的坐标。
• 2 p: 求出部件 $p$ 所在的坐标。

输入格式

输入按以下格式从标准输入给出。

$N$ $Q$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

每个查询是以下两种格式之一。

$1$ $C$

$2$ $p$

输出格式

设第 2 类查询的次数为 $q$,输出 $q$ 行。

第 $i$ 行输出第 $i$ 个该查询答案的坐标 $(x,y)$,即 $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

注意,多个部件可能位于同一坐标。

数据范围

• $2 \leq N \leq 10^6$
• $1 \leq Q \leq 2 \times 10^5$
• 第 1 类查询中,$C$ 是 R、L、U、D 之一
• 第 2 类查询中,$1 \leq p \leq N$
• 输入中的所有数值均为整数