题目描述

小高创建了一个游戏，玩家在坐标平面上控制一条龙。龙由$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$
$query_1$
$\vdots$
$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

样例1解释

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

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

数据范围

$2 ≤ N ≤ 10^6$
$1 ≤ Q ≤ 2×10^5$
对于第一种查询，$C$是$R$、$L$、$U$和$D$之一。
对于第二种查询，$1 ≤ p ≤ N$，所有输入的数值都是整数。

来源

• AtCoder ABC335C