该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

分拣系统 (sort)

题目描述

Y 同学正在设计一套自动化物流分拣系统。该系统包含 $n$ 条并行的传送带，编号为 $1, 2, \dots, n$。

每条传送带被划分为 $m+1$ 个工位。我们将第 $a$ 条传送带的第 $b$ 个工位记为 $(a, b)$。初始状态下，每条传送带内部的工位是连通的，即对于所有的 $1 \le a \le n$ 和 $1 \le b \le m$，工位 $(a, b)$ 与 $(a, b+1)$ 之间由一条垂直的传送轨道相连。

为了实现跨轨道分拣，Y 同学需要执行 $q$ 次操作。操作分为以下两类：

1. 安装分流器：在相邻两条传送带的相同高度处安装一个分流器。具体地，在工位 $(a, b)$ 与 $(a+1, b)$ 之间建立一条双向水平连接轨道，其中 $1 \le a < n, 1 \le b \le m$。系统要求在任何时刻，每个工位最多只能连接一个分流器。
2. 分拣路径模拟：一个待分拣的包裹从起点 $(a, 1)$ 进入系统。包裹的移动逻辑如下：
   • 如果当前工位连接了一个在本次分拣任务中尚未经过的分流器，包裹将通过该分流器移动到相邻传送带的对应工位（即从 $(a, b)$ 移动到 $(a \pm 1, b)$）；
   • 否则，包裹将沿着垂直轨道移动到当前传送带的下一个工位 $(a, b+1)$；
   • 当包裹到达任何一条传送带的第 $m+1$ 个工位时，分拣过程结束。

需要注意的是，分流器是否被“经过”在每次查询中是独立判定的。Y 同学希望对于每次类型 2 的查询，你能告诉他包裹最终会停留在哪一条传送带上。

输入格式

第一行包含三个正整数 $n, m, q$，分别表示传送带数量、分拣工位长度以及操作总数。

接下来 $q$ 行，每行描述一个操作：

• 1 a b：表示在工位 $(a, b)$ 与 $(a+1, b)$ 之间安装一个分流器。
• 2 a：表示一个包裹从 $(a, 1)$ 开始分拣，询问其最终到达的传送带编号。

输出格式

对于每个类型 2 的查询，输出一行一个整数，表示包裹最终停留的传送带编号。

样例

样例输入 #1

3 4 13
2 2
1 1 3
2 1
2 2
2 3
1 2 4
2 1
2 2
2 3
1 2 1
2 1
2 2
2 3

样例输出 #1

2
2
1
3
3
1
2
3
2
1

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n, m, q \le 10^5$，$1 \le a \le n$，$1 \le b \le m$。对于所有的类型 1 操作，满足 $1 \le a < n$ 且不会在同一工位重复安装分流器。

• 特殊性质 A：所有的类型 1 操作（安装分流器）均发生在任何类型 2 操作（分拣模拟）之前。
• 特殊性质 B：保证所有安装的分流器其高度 $b$ 均满足 $b \le 100$。