問題文

長さ $N$ の数列 $P=(1,2,\dots,N)$ があります。
また、 $K$ 個の操作があり、操作 $i$ は $P_{A_i}$ と $P_{B_i}$ を入れ替える操作です。
各 $j=1,2,\dots,Q$ について、操作 $L_j,L_j+1,\dots,R_{j}$ をこの順に行ったときの $P_{X_j}$ を求めてください。
ただし、どの $j$ でも操作の開始前は $P=(1,2,\dots,N)$ であることに注意してください。

制約

• 入力は全て整数である。
• $2\le N\le 4\times 10^{5}$
• $1\le K\le 2\times 10^{5}$
• $1\le Q\le 2\times 10^{5}$
• $1\le A_i<B_i\le N\ (1\le i\le K)$
• $1\le L_j\le R_j\le K\ (1\le j\le Q)$
• $1\le X_j\le N\ (1\le j\le Q)$

入力

$N$ $K$ $Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_K$ $B_K$
$L_1$ $R_1$ $X_1$
$L_2$ $R_2$ $X_2$
$\vdots$
$L_Q$ $R_Q$ $X_Q$

出力

$Q$ 行出力してください。
$j$ 行目には操作 $L_j,L_j+1,\dots,R_{j}$ をこの順に行ったときの $P_{X_j}$ を出力してください。

サンプル

3 3 2
1 2
1 3
2 3
2 2 1
1 3 2

3
2

6 9 8
1 5
1 4
4 5
1 4
4 5
1 4
4 5
1 3
4 5
4 6 3
5 7 5
3 8 5
4 6 3
3 6 2
8 9 5
3 6 2
1 4 5

3
1
5
3
2
4
2
5