Dragon Management in Valyria

In the legendary land of Valyria, dragons are bred in various breeds. Each dragon has a power level and belongs to a particular breed. You are tasked with processing two types of operations:

1. Operation "1 p x": Add a dragon with power level (p) to breed (x).
2. Operation "2 x y": Compare the total power of breed (x) and breed (y). The breed with the higher cumulative power is considered superior; if both have equal power, the breed with the smaller numerical label is considered stronger.

Initially, you are given a list of dragons with their power levels and breeds. Then, a series of queries is provided. For each query of type 2, output the winning breed on a new line.

Mathematically, let (P(x)) denote the total power of breed (x). Then for a query of type 2 involving breeds (x) and (y), the answer is determined as follows: [ \text{answer} = \begin{cases} x, & \text{if } P(x) > P(y) \ y, & \text{if } P(x) < P(y) \ \min(x, y), & \text{if } P(x) = P(y) \end{cases} ]

Your solution should read input from standard input and output the results to standard output.

inputFormat

The first line contains three integers (n), (k), and (q) separated by spaces:

• (n): The number of dragons initially present.
• (k): The total number of breeds.
• (q): The number of queries.

The next (n) lines each contain two integers, representing the power level and breed of a dragon.

The following (q) lines each represent a query and are in one of the following formats:

• For an addition query: 1 p x (add a dragon with power (p) to breed (x)).
• For a comparison query: 2 x y (compare breeds (x) and (y)).

outputFormat

For each query of type 2, output the result (the breed number that is superior) on a new line.## sample

7 3 6
10 2
5 1
8 2
7 1
6 3
3 3
12 2
2 2 1
2 3 1
1 9 1
2 1 2
2 2 3
2 1 3

2
1
2
2
1