Swap

题号：NC282807
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

int work(int l, int r, int k){
	int p[N + 5];
	for (int i = 1; i <= n; i++) p[i] = i;
	for (int i = l; i <= r; i++) swap(p[a[i]], p[b[i]]);
	return p[k];
}

给定 $n,m,q,a_1\dots a_m,b_1\dots b_m$ ， $q$ 组询问 $\text{work}(l,r,k)$ 的值。

$1 \leq n,m,q \leq 10^6$ 。

$1\leq a_i, b_i, k \leq n, 1\leq l \leq r \leq m$ 。

输入描述:

输入描述 第一行，三个整数，表示 。

接下来  行，每行两个整数，表示 。

接下来  行，每行三个整数，表示一组询问中的参数 。

输出描述:

共  行，每行一个整数，依次表示每组询问的答案，

示例1

输入

复制

输出

复制