Hero's Journey in Erathia

There are \(n\) countries numbered from \(1\) to \(n\) in Erathia. Each country is represented as a chain with \(m+1\) nodes numbered from \(1\) to \(m+1\). Initially, every country has streets connecting node \((a,b)\) and \((a,b+1)\) for \(1 \le b \le m\). No bridges connect nodes between different countries at the start.

You are given \(q\) queries. Each query is in one of the two following formats:

• Type 1: 1 a b where \(1 \le a < n\) and \(1 \le b \le m\). Build a bridge between node \((a,b)\) in country \(a\) and node \((a+1,b)\) in country \(a+1\). It is guaranteed that at any moment, each node is connected with at most one bridge.
• Type 2: 2 a where \(1 \le a \le n\). A hero begins his journey from node \((a,1)\) in country \(a\). At each step, if the current node \((x,y)\) has an unvisited bridge, the hero takes it; otherwise, he moves to the right, i.e. to \((x,y+1)\). Once he reaches any node numbered \(m+1\), his journey terminates. Note: The visited status of bridges is reset for each hero query.

For each Type 2 query, output the country number where the hero stops. It can be proved that the hero's route is unique under these constraints.

inputFormat

The first line contains three integers \(n\), \(m\), and \(q\), representing the number of countries, the number of streets (each country has \(m+1\) nodes), and the number of queries, respectively.

Each of the following \(q\) lines describes a query in one of the following formats:

• 1 a b — Build a bridge between node \((a,b)\) and node \((a+1,b)\).
• 2 a — Perform a hero query starting from node \((a,1)\).

outputFormat

For each query of Type 2, print a single integer on a new line indicating the country number where the hero ends his journey.

sample

3 3 3
1 1 1
1 2 2
2 1

3