P9358 [ICPC 2022 Xi'an R] Bridge

Erathia 大陆上有 $n$ 个国家，从 $1$ 到 $n$ 编号。每个国家可以看成由 $m + 1$ 个结点组成的链，结点从 $1$ 到 $m + 1$ 编号。结点 $(a, b)$ 和 $(a, b + 1)$ 由一条街道连接，其中 $(a, b)$ 表示国家 $a$ 的第 $b$ 个结点。一开始，国家之间没有桥。 你需要处理 $q$ 个操作： - $1\ a\ b$（$1\leq a < n$，$1\leq b\leq m$）：在 $(a, b)$ 和 $(a + 1, b)$ 之间建造一座桥。**保证每个结点最多和一座桥相连**。 - $2\ a$（$1\leq a\leq n$）：一名英雄走过 Erathia 大陆。他从 $(a, 1)$ 出发。如果这名英雄当前在结点 $(x, y)$ 且有一座未被访问过的桥与之连接，那么他会走过这个桥到达桥的另一端，否则他会走到 $(x, y + 1)$。一旦他到达某个国家的第 $m + 1$ 个结点，他就会停下来。注意两个询问之间的 “未被访问过的桥” 是独立的。 你的任务是对每个操作 $2$ 求出英雄最终所在的国家。 $1\leq n, m, q\leq 10 ^ 5$。

第一行三个整数 $n, m, q$。

对于每个操作 $2$，输出一行一个整数表示答案。

**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem A. **Author**: MonkeyKing.