分数: 300 点
问题陈述
Takahashi 创建了一款游戏,玩家可以在坐标平面上控制龙。
龙由以下组成 N 零件编号 1 to N,含部分 1 被称为 头.
最初,部分 i 位于坐标处 (i,0)。工艺流程 Q 查询如下。
1 C: 将头部移动 1 方向 C。在这里, C 是其中之一R,L,U,和D,代表正数 x- 方向,负 x- 方向,正 y- 方向,负 y- 方向,分别。除头部外的每个部分都跟随其前面的部分移动。也就是说,部分 i (2\leq i \leq N) 移动到零件所在的坐标 i-1 是在搬家之前。2 p: 查找零件的坐标 p.
约束
- 2 \leq N \leq 10^6
- 1 \leq Q \leq 2\times 10^5
- 对于第一类查询, C 是其中之一
R,L,U,和D. - 对于第二种类型的查询, 1\leq p \leq N.
- 所有数字输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q
每个查询采用以下两种格式之一:
1 C
2 p
输出
打印 q 行,其中 q 是第二类查询的数量。
的 i- 第行应包含 x 和 y 用空格分隔,其中 (x,y) 是以下问题的答案 i-第一个这样的查询。
示例输入 1
5 9 2 3 1 U 2 3 1 R 1 D 2 3 1 L 2 1 2 5
示例输出 1
3 0 2 0 1 1 1 0 1 0
每次处理第二类查询时,各部分位于以下位置:

请注意,同一坐标处可能存在多个零件。