贪吃蛇

题目描述

贪吃蛇游戏是总所周知的游戏，游戏中玩家可以在坐标平面上控制一条蛇。

这条蛇包含N个编号为1到N的部位，而部位1被叫做“头”。

初始状态下，第i个部位位于坐标（i,0）。下面你需要回答Q个询问。

• 1 C：蛇的头部向方向C移动一个单位长度。C可能是R、L、U、D中的一个字母，分别代表x轴正方向、x轴负方向、y轴正方向、y轴负方向。其他的所有部位都会跟随上一个部位移动。形式化地，编号为i的部位会移动到编号为i−1的部位先前所在的位置。
• 2 p：输出编号为p的部位的坐标。

你需要对所有询问2做出回答。

输入描述

第一行两个整数N、Q。

数据范围：

• $ 1 \leq N \leq 10^5 $
• $ 1 \leq Q \leq 10^5 $
• 第一种询问，C可能是R、L、U、D中的一个字母
• 第二种询问， $ 1 \leq p \leq N $

输出描述

对于每个询问2 p，输出部位p当前的坐标

提示

样例1图解：