题目描述

小明正在开发一个贪吃蛇游戏，他需要模拟蛇的移动逻辑。在这个游戏中，蛇的身体由 $N$ 个连续的格子组成，每个格子在二维网格中都有一个位置。

蛇的头部编号为 $1$ ，尾部编号为 $N$ 。初始时，蛇排列在网格上的 $x$ 轴（水平方向是 $x$ 轴，垂直方向是 $y$ 轴）：

第 $i$ 个身体段初始位于坐标 $(i,\ 0)$ ，头部在 $(1,\ 0)$ ，尾部在 $(N,\ 0)$ 。

蛇的移动规则如下：每次移动，蛇的头部会向特定方向移动一格，而其他身体段则会移动到前一个身体段之前所在的位置。

游戏记录了一连串操作，包括两种类型：

移动操作 1 C：控制蛇的头部向方向 $C$ 移动一格。方向 $C$ 可以是：

$R$ （右）： $x$ 坐标增加 $1$ ；

$L$ （左）： $x$ 坐标减少 $1$ ；

$U$ （上）： $y$ 坐标增加 $1$ ；

$D$ （下）： $y$ 坐标减少 $1$ ；

移动后，每个身体段会移动到它前一个身体段移动前的位置。

查询操作 2 p：查询第 $p$ 个身体段当前所在的位置坐标 $(x,\ y)$ 。

请你帮助小明编写程序，处理所有操作，并回答每个查询操作。

输入格式

第一行包含两个整数 $N$ 和 $Q$ ，分别表示蛇的身体长度和操作数量。

接下来 $Q$ 行，每行描述一个操作，格式如上所述。

对于每个查询操作，输出一行，包含两个整数 $x$ 和 $y$ ，表示查询的身体段的坐标。

初始时，蛇的身体在 $(1,0),(2,0),\ldots,(5,0)$ 上排成一条线。

第一条查询 2 3，第三节是 $(3,0)$ ；

向上移动后，新的头部是 $(1,1)$ ，原第 $1$ 节变成第 $2$ 节，以此类推；

之后查询 2 3 时，该节变成了之前的 $(2,0)$ ，以此类推。

$1 \leq N, Q \leq 10^6$

保证操作合法。