小珅的星际赛马模拟器

题目描述

在智亦珅泽教育的“星际奥林匹克竞赛”中，小珅老师作为赛事总监，正在为即将到来的“跨星系速度节”做最后的准备工作。本届速度节的压轴项目是——星际赛马！

与传统的赛马不同，本次比赛的规则充满了科幻色彩。赛场上一共有 $n$ 匹性能各异的赛马，依次编号为 $1 \sim n$。小珅拿出了两台高科技量子骰子来决定比赛的进程：

• 第一台骰子有 $n$ 个面，点数范围为 $1 \sim n$，掷出的结果 $a$ 代表参赛马的编号。
• 第二台骰子有 $2 \times m + 1$ 个面，点数范围为 $-m \sim m$，掷出的结果 $b$ 代表前进（或后退）的距离。若 $b \ge 0$，表示前进 $b$ 个单位距离；若 $b < 0$，表示后退 $|b|$ 个单位距离。需要注意的是，当马匹后退到起点（距离为0）时，将无法继续后退。

比赛开始前，所有马匹均位于起点（距离为0）。接下来，小珅会下达 $q$ 次指令，指令共分为三种类型，参数分别如下：

• 1 a b：这是第一种指令（移动指令）。小珅掷一次骰子，将编号为 $a$ 的马匹前进（或后退）$|b|$ 个单位距离。
• 2 a：这是第二种指令（查询指令）。小珅询问编号为 $a$ 的马匹当前距离起点的距离是多少。
• 3 r：这是第三种指令（排名查询指令）。小珅询问当前排名第 $r$ 位的马匹编号是多少。

排名规则：距离起点越远的马匹排名越靠前（即距离 $d_i$ 越大，名次越高）；如果距离相同，则编号较小的马匹排名更靠前。

小珅希望你能帮他编写一个模拟程序，忠实记录每一次指令的执行，并在遇到查询指令时给出准确的反馈。

输入格式

第一行包含三个整数 $n, m, q$，分别表示马匹的数量、第二颗骰子的最大面值以及指令的总次数。

接下来 $q$ 行，每行包含 $2 \sim 3$ 个正整数，表示一次指令，指令格式详见题目描述。

输出格式

对于每次的第二种指令（查询距离）和第三种指令（查询排名），输出一行一个整数，表示对应的查询结果。

输入输出样例

输入 #1

5 6 6
1 2 3
1 3 3
2 2
3 3
1 5 4
3 3

输出 #1

3
1
3

输入 #2

3 6 7
1 2 4
3 3
1 3 -6
3 1
2 3
1 3 4
2 2

输出 #2

3
2
0
4

说明/提示

• 对于 $30\%$ 的数据，满足 $1 \le n \le 200$，$1 \le m \le 100$，$1 \le q \le 500$，$1 \le b \le m$。
• 对于 $50\%$ 的数据，满足 $1 \le n \le 2000$，$1 \le m \le 1000$，$1 \le q \le 2000$。
• 对于 $70\%$ 的数据，满足 $1 \le n \le 8000$，$1 \le m \le 1000$，$1 \le q \le 50000$。
• 对于 $100\%$ 的数据，满足 $1 \le n \le 10000$，$1 \le m \le 10^9$，$1 \le q \le 2 \times 10^5$，$1 \le a, r \le n$，$-m \le b \le m$。 保证在所有 $q$ 次操作中，至多只有 $5000$ 次操作属于第一种（移动）指令