在 Erathia 有 $n$ 个国家，编号从 $1$ 到 $n$。每个国家都可以看作是一个包含 $m+1$ 个节点的链，节点编号从 $1$ 到 $m+1$。最初，节点 $(a, b)$ 与节点 $(a, b+1)$ 之间由街道相连，其中 $(a, b)$ 表示第 $a$ 个国家的第 $b$ 个节点。起初，任意两个国家之间都没有桥梁。

你需要处理 $q$ 个查询，查询分为以下两种类型：

• $1 \ a \ b$ ($1 \le a < n, 1 \le b \le m$)：在节点 $(a, b)$ 和节点 $(a+1, b)$ 之间建造一座桥。保证在任何时候，每个节点最多连接一座桥。
• $2 \ a$ ($1 \le a \le n$)：一位英雄将在 Erathia 中行走。这位英雄从 $(a, 1)$ 出发。如果英雄当前位于 $(x, y)$ 且有一个与他相连的未访问过的桥，他会通过这座桥；否则，他会前往 $(x, y+1)$。一旦他到达任何国家的第 $(m+1)$ 个节点，他就会停止。请注意，“未访问过的桥”对于每个查询是独立判断的。

你的任务是对于第二种类型的查询，输出英雄最终所在的国家编号。可以证明，在这些约束条件下，英雄的路线总是唯一的。

输入格式

第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n, m, q \le 10^5$)。

接下来的 $q$ 行，每行代表一个上述格式的查询。

输出格式

对于每个类型为 $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