410688: GYM104077 A Bridge

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.

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