← 返回题目列表

AtCoder · abc335_c

E. 龙追踪

中文机器翻译题面 查看原题

分数: 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

每次处理第二类查询时,各部分位于以下位置:

Figure

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