010 - 化学物質アルファ

問題

アイヅ製薬では日々化学物質の研究がなされています。いま研究をしているのは、$1$番から$N$番の分子が左端から右端へ直線状にならんだ構造をしている化学物質、コードネーム「アルファ」です。

アイヅ製薬の開発した技術を使えば、アルファを構成する分子の位置を入れ替えることができます。入れ替えは決まった手順でしか行うことができませんが、その手順の途中から始めて途中で終わることもできます。左端から$a$番目と$b$番目の分子を入れ替える操作を$(a,b)$と書くとします。たとえば、$N=5$で決まった手順が$(1,3),(2,5),(4,3),(1,5)$のとき、$1$番目の操作$(1,3)$から始めて$3$番目の操作$(4,3)$で終わることも、$2$番目の操作$(2,5)$から始めて$4$番目の操作$(1,5)$で終わることもできます。

あなたは、アルファの分子の入れ替え手順の中の開始位置と終了位置を選んでシミュレーションを行い、入れ替え後の分子の状態を調べることにしました。

アルファの分子の入れ替え手順が与えられる。シミュレーションを何度か行ったとき、各シミュレーションでの分子の位置について質問に答えるプログラムを作成せよ。質問は次の1.または2.の形をしている。

1. 終了後に左端から$i$番目に位置している分子は、最初は何番目に位置していたか。
2. 最初に$i$ 番目に位置していた分子が終了後にどの位置に来ているか。

ただし、各シミュレーションは、アルファの初期状態（$1$番から$N$番の分子が左端から右端へ直線状にならんだ状態）から始めるものとする。

入力

入力は以下の形式で与えられる。

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

１行目にアルファを構成する分子の数$N$ ($2 \leq N \leq 100,000$)、入れ替え手順の長さ$K$ ($1 \leq K \leq 100,000$)、入れ替え後の分子の状態を調べる回数$Q$ ($1 \leq Q \leq 100,000$)が与えられる。続く$K$行に入れ替え手順の中の各操作$a_i,b_i$ ($1 \leq a_i,b_i \leq N$, $a_i \ne b_i$)が与えられる。$i$番目の操作は、左端から$a_i$番目と$b_i$番目の分子を入れ替える操作を表す。続く$Q$行に、入れ替え終了後の分子の状態を尋ねる質問が与えられる。各$query_i$は以下のいずれかの形式で与えられる。

1 $s$ $t$ $x$

または

2 $s$ $t$ $x$

最初の数字が1の場合、入れ替え手順の中の入れ替えを$s$番から$t$番($1 \leq s \leq t \leq K$)まで行った後に、左側から$x$番目($1 \leq x \leq N$)の分子の番号が何番か尋ねる質問を表す。最初の数字が2の場合、入れ替え手順の中の入れ替えを$s$番から$t$番($1 \leq s \leq t \leq K$)まで行った後に、$x$番($1 \leq x \leq N$)の分子が左から数えて何番目にあるか尋ねる質問を表す。

出力

各質問に対して、答えを１行に出力する。

入出力例

入力例

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

入れ替え手順は$(1,3),(2,5),(3,4),(2,4),(2,5)$である。
$1$番目から$6$番目の質問では、手順の$1$番目($s=1$)から$5$番目($t=5$)まですべて行った場合なので、入れ替え後の状態はすべて共通で以下のようになる。

初期状態　1 2 3 4 5 6
$(1,3)$の後 3 2 1 4 5 6
$(2,5)$の後 3 5 1 4 2 6
$(3,4)$の後 3 5 4 1 2 6
$(2,4)$の後 3 1 4 5 2 6
$(2,5)$の後 3 2 4 5 1 6

$7$番目の質問では$s=3,t=4$なので、入れ替え後の状態は以下のようになる。分子番号$2$番は左から数えて$4$番目にあるので、答えは4になる。

初期状態　1 2 3 4 5
$(3,4)$の後 1 2 4 3 5
$(2,4)$の後 1 3 4 2 5

$8$番目の質問では$s=1,t=1$なので、入れ替え後の状態は以下のようになる。

初期状態　1 2 3 4 5
$(1,3)$の後 3 2 1 4 5