Background

众所周知，MrPython 在高一上学期的皮炎通红语考试中没能拿到满分的成绩，可喜可贺可喜可贺。

他非常高兴，于是想要你帮他解决一个伪代码阅读题。

Description

给定 $n,m$ 和长度为 $m$ 的数组 $a,b$，定义函数 $\text{SOLVE}$ 如下：

$$\begin{array}{ll} \text{SOLVE}(l,r,k) \\ ~ 1 \quad p = \left( 1,2,\dots,n \right) \\ ~ 2 \quad \textbf{for} ~~ i=l ~~ \textbf{to} ~~ r \\ ~ 3 \quad \qquad \text{exchange} ~ p_{a_i} \text{with} ~ p_{b_i} \\ ~ 4 \quad \textbf{return} ~~ p_k \end{array} $$

你需要回答 $q$ 个问题，每次给定 $l_j,r_j,k_j$，你需要求出 $\text{SOLVE}(l_j,r_j,k_j)$ 的值。

Constraints and Subtasks

对于全部测试点，满足：

• $1 \leq n,m,q \leq 10^6$
• $1 \leq a_i,b_i,k_j \leq n$
• $1 \leq l_j \leq r_j \leq m$
• 所有输入数据都是整数。

另外，还有一些测试点满足特殊要求。

分值	$n\leq$	$m\leq$	$q\leq$	特殊性质
$20\%$	$3000$	$3000$	$3000$
$20\%$	$10^6$	$10^6$	$10^6$	$l_j=1$
$20\%$				$r_j=m$
$40\%$

---

Input

输入内容从标准输入中给出，格式如下：

$ \boxed{\begin{aligned} & n {\quad} m {\quad} q \\ & a_1 {\quad} b_1 \\ & a_2 {\quad} b_2 \\ & \vdots \\ & a_m {\quad} b_m \\ & l_1 {\quad} r_1 {\quad} k_1\\ & l_2 {\quad} r_2 {\quad} k_2\\ & \vdots \\ & l_q {\quad} r_q {\quad} k_q \end{aligned}} $

Output

输出 $n$ 行正整数，第 $i$ 行表示第 $i$ 个问题的答案。

Samples

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

3
5
1
3
2