問題文

正整数 $N,M$ と $1$ 以上 $N$ 以下の整数からなる整数列 $(L_1,L_2,\dotsc,L_M),(R_1,R_2,\dotsc,R_M)$ が与えられます。

これから以下の問題について考えます。

長さ $N$ の数列 $(A_1,A_2,...,A_N)$ があります。初め $A_i=i$ です。

$k=1,2,\dotsc,t$ の順番に $A$ の $L_{((k-1)\bmod M)+1}$ 番目と $R_{((k-1)\bmod M)+1}$ 番目の要素を入れ替えるという操作を行った後の $A_x$ を求めてください。

この問題には $Q$ 個のシチュエーションが考えられます。$i$ 個目のシチュエーションでは $t=T_i,x=X_i$ として上記の問題に答えてください。

制約

• $2\leq N\leq 10^5$
• $1\leq M,Q\leq 2\times 10^5$
• $1\leq L_i< R_i\leq N$
• $1\leq X_i\leq N$
• $1\leq T_i\leq 10^{18}$
• 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

入力

$N\ M\ Q$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_M\ R_M$
$T_1\ X_1$
$T_2\ X_2$
$\vdots$
$T_Q\ X_Q$

出力

$Q$ 行出力してください。

$i\ (1\leq i\leq Q)$ 行目には $i$ 個目のシチュエーションに対する答えを出力してください。

サンプル

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

4
3
2

2 1 2
1 2
1 1
2 1

2
1

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

6
6
6

1000 5 6
159 314
159 411
411 892
169 231
29 159
314159 314
159411 159
411892 411
169231 169
29159 29
1000000000000000000 1

29
29
411
169
411
1