Chemical Substance Alpha

　

At Aizu Pharmaceutical, we are constantly researching chemical substances. The chemical we are currently researching is code-named "alpha," which has a structure consisting of molecules numbered $1$ through $N$ arranged in a straight line from leftmost to rightmost.

Using the technology developed by Aizu Pharmaceuticals, the positions of the molecules that make up Alpha can be swapped. The swapping can only be done in a fixed procedure, but it can also be started and finished in the middle of that procedure. Let's write (a,b) for the operation of swapping the a-th and b-th molecules from the left end. For example, if $N=5$ and the fixed sequence is (1,3),(2,5),(4,3),(1,5), you can start with the first operation (1,3) and end with the third operation (4,3), or you can start with the second operation (2,5) and end with the fourth operation (1,5).

You have chosen the start and end positions in the alpha molecule replacement procedure to run the simulation and investigate the state of the molecule after the replacement.

You are given an alpha molecular replacement procedure. Write a program that answers questions about the position of the molecule in each simulation when you run the simulation several times. The questions can be of the form 1. or 2. below.

1. What was the initial position of the molecule that is the i-th position from the left end after the end of the simulation?
2. What position does the molecule that was initially positioned i-th come to after termination?

Note that each simulation starts from the initial state of alpha (molecules numbered $1$ to $N$ are lined up in a straight line from the leftmost to the rightmost position).

Input

The input is given in the following form.

$N$ $K$ $Q$
$a_1$ $b_1$
$a_2$ $b_2$
:
$a_K$ $b_K$
$query_1$
$query_2$
:
$query_Q$

The first line gives the number of molecules in alpha $N$ ($2 \leq N \leq 100,000$), the length of the swapping procedure $K$ ($1 \leq K \leq 100,000$), and the number of times to check the state of the molecules after swapping $Q$ ($1 \leq Q \leq 100,000$). In the following $K$ lines, each operation $a_i,b_i$ ($1 \leq a_i,b_i\leq N, a_i \ne b_i$) in the transposition procedure is given. $i$-th operation represents the operation to transpose the $a_i$-th and $b_i$-th molecules from the left end. In the following $Q$ lines, questions are given asking the state of the molecules after the swap. Each $query_i$ is given in one of the following forms.

1 $s$ $t$ $x$

or

2 $s$ $t$ $x$

If the first number is 1, it represents a question that asks what the number of the $x$-th molecule from the left side ($1 \leq x \leq N$) is after performing the transposition from $s$-th to $t$-th ($1 \leq s \leq t \leq K$) in the transposition procedure. If the first number is 2, it represents a question that asks where is the $x$-th ($1 \leq x \leq N$) molecule from the left side after performing the transposition in the transposition procedure from $s$-th to $t$-th ($1 \leq s \leq t \leq K$)

Output

For each question, print the answer in a line.

Sample Input and Output

Sample Input

6 5 8
1 3
2 5
3 4
2 4
2 5
1 1 5 1
1 1 5 2
1 1 5 3
1 1 5 4
1 1 5 5
1 1 5 6
2 3 4 2
1 1 1 1

Sample Output

3
2
4
5
1
6
4
3

The replacement procedure is $(1,3),(2,5),(3,4),(2,4),(2,5)$.
For the $1$th through $6$th questions, since we have done everything from the $1$th ($s=1$) through the $5$th ($t=5$) steps, the state after replacement is common to all and is as follows.

Initial state　1 2 3 4 5 6
After $(1,3)$ 3 2 1 4 5 6
After $(2,5)$ 3 5 1 4 2 6
After $(3,4)$ 3 5 4 1 2 6
After $(2,4)$ 3 1 4 5 2 6
After $(2,5)$ 3 2 4 5 1 6

In the $7$th question, $s=3,t=4$, so the state after replacement is as follows. Since the numerator number $2$ is at the $4$th position counting from the left, the answer is 4.

Initial state　1 2 3 4 5
After $(3,4)$ 1 2 4 3 5
After $(2,4)$ 1 3 4 2 5

In the $8$th question, $s=1,t=1$, so the state after replacement is as follows.

Initial state　1 2 3 4 5
After $(1,3)$ 3 2 1 4 5

---