Chemical Substance Alpha

At Aiz Pharmaceutical, research on chemical substances is carried out every day. I am currently studying the code name "Alpha", a chemical substance that has a structure in which molecules from $1$ to $N$ are linearly arranged from the left end to the right end.

Using the technology developed by Aiz Pharmaceutical, the positions of the molecules that make up alpha can be swapped. Swapping can only be done in a fixed procedure, but you can start in the middle of the procedure and end in the middle. Suppose that the operation of exchanging the $a$ and $b$ th numerator from the left end is written as $(a, b)$. For example, when the procedure determined by $N = 5$ is $(1,3), (2,5), (4,3), (1,5)$, the $1$ th operation $(1,3) ) Starting with$ and ending with $3$ th operation $(4,3)$, or starting with $2$ th operation $(2,5)$ and ending with $4$ th operation $(1,5)$ You can also.

You decided to select the start and end positions in the alpha molecule replacement procedure and perform a simulation to investigate the state of the molecule after replacement.

A procedure for replacing the molecule of alpha is given. Create a program that answers questions about the position of molecules in each simulation after several simulations. The question has the form of 1. or 2.

1. At the beginning, what position was the molecule located at the $i$ position from the left end after the end?
2. At what position is the molecule that was originally located at the $i$ position after the end?

However, each simulation shall start from the initial state of alpha (a state in which molecules from $1$ to $N$ are linearly arranged from the left end to the right end).

input

The input is given in the following format.

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

The number of molecules that make up alpha in the first line $N$ ($2 \ leq N \ leq 100,000$), the length of the replacement procedure $K$ ($1 \ leq K \ leq 100,000$), and the state of the molecules after replacement Given the number of times to look up $Q$ ($1 \ leq Q \ leq 100,000$). The following $K$ line gives each operation $a_i, b_i$ ($1 \ leq a_i, b_i \ leq N$, $a_i \ ne b_i$) in the swap procedure. The $i$ th operation represents an operation of swapping the $a_i$ th and $b_i$ th numerator from the left end. The following $Q$ line is given a question asking the state of the molecule after the replacement. Each $query_i$ is given in one of the following formats:

1 $s$ $t$ $x$

Or

2 $s$ $t$ $x$

If the first number is 1, the swap in the swap procedure is from $s$ to $t$ ($1 \ leq s \ leq t \ leq K$) and then the $x$ th ($1) from the left. \ leq x \ leq N$) represents a question asking what the numerator number is. If the first number is 2, the swap in the swap procedure is from $s$ to $t$ ($1 \ leq s \ leq t \ leq K$) and then $x$ ($1 \ leq). x \ leq N$) represents a question asking what number the numerator is from the left.

output

Output the answer to each question on one line.

Examples

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

Output

3 2 4 5 1 6 4 3

Input

None

Output

None

inputFormat

input

The input is given in the following format.

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

The number of molecules that make up alpha in the first line $N$ ($2 \ leq N \ leq 100,000$), the length of the replacement procedure $K$ ($1 \ leq K \ leq 100,000$), and the state of the molecules after replacement Given the number of times to look up $Q$ ($1 \ leq Q \ leq 100,000$). The following $K$ line gives each operation $a_i, b_i$ ($1 \ leq a_i, b_i \ leq N$, $a_i \ ne b_i$) in the swap procedure. The $i$ th operation represents an operation of swapping the $a_i$ th and $b_i$ th numerator from the left end. The following $Q$ line is given a question asking the state of the molecule after the replacement. Each $query_i$ is given in one of the following formats:

1 $s$ $t$ $x$

Or

2 $s$ $t$ $x$

If the first number is 1, the swap in the swap procedure is from $s$ to $t$ ($1 \ leq s \ leq t \ leq K$) and then the $x$ th ($1) from the left. \ leq x \ leq N$) represents a question asking what the numerator number is. If the first number is 2, the swap in the swap procedure is from $s$ to $t$ ($1 \ leq s \ leq t \ leq K$) and then $x$ ($1 \ leq). x \ leq N$) represents a question asking what number the numerator is from the left.

outputFormat

output

Output the answer to each question on one line.

Examples

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

Output

3 2 4 5 1 6 4 3

Input

None

Output

None

样例

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

3
2
4
5
1
6
4
3

</p>