题目描述

There are $n$ countries numbered from $1$ to $n$ in Erathia. Each country can be regarded as a chain with $m+1$ nodes numbered from $1$ to $m+1$. Initially, node $(a, b)$ is connected with node $(a, b + 1)$ by a street where node $(a, b)$ denotes the $b$-th node of the $a$-th country. There are no bridges between any two countries at first.

You need to process $q$ queries of the following two types.

• $1\ a\ b$ ($1\leq a < n, 1\leq b\leq m$). Build a bridge between node $(a, b)$ and node $(a + 1, b)$. It is guranteed that at any time, each node is connected with at most one bridge.
• $2\ a$ ($1\leq a\leq n$). A hero will walk through Erathia. This hero starts from $(a, 1)$. If the hero is at $(x, y)$ and there is a unvisited bridge connected to him, he passes it, or he goes to $(x, y + 1)$. Once he arrived the $(m+1)$-th node of any conutry, he stops. Please note that 'unvisited bridge' is independently judged for each query.

Your task is to print which country the hero is in at last for the second kind of query. It can be proved that the hero's route is always unique under these constraints.

输入格式

The first line contains three integers $n$, $m$ and $q$ ($1 \leq n, m, q \leq 10 ^ 5$).

Each of the following $q$ lines represents a query with format described above.

输出格式

For each query of type $2$, output a line with an integer representing the answer.

题目大意

题目描述

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$。

接下来 $q$ 行，每行若干个整数表示一组询问。格式见题目描述。

输出格式

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

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

2
2
1
3
3
1
2
3
2
1

提示

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

Author: MonkeyKing.