该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

【cy篇 第一回】

wjq 是个热爱数列的 OIer。

考试的那天，cy和wjq被命运安排到了同一个考场。

数学考试前的20分钟。

cy和wjq没有像其他人一样紧张地复习 (抱佛脚) 。而是正在在座位上做解数列题的游戏。

“据说数学考试前这样可以很好地带动思维，有利接下来考试的发挥呢。”

“不过要是解不出来的话……那不就很影响考试心情的嘛……”

“没事。一定能解出来的！”

于是，在这仅剩的20分钟内，他们开始向这数列题发起挑战。

那个静谧的下午，阳光缓缓地透过教室外的树梢，温暖地洒落路旁。

题目描述

wjq 给了你一个数列。

这个数列长度为 \(n\)，初始值为 \(1,2,3,4,\cdots, n\)。

现在wjq对这个数列进行操作。每一次操作有 \(m\) 个子操作，每一个子操作格式如下：

a b，表示将位置 \(a\) 和位置 \(b\) 的两个数字交换

每一个操作就是按照输入顺序依次执行每一个子操作。

然后wjq有 \(q\) 个询问，每一个询问会输入两个数 \(k,p\)，要你输出序列操作 \(k\) 次后数字 \(p\) 的位置。

当然每一次询问后序列会恢复初始值，你也可以看做每次询问都是独立的，互不干扰。

输入格式

第一行，三个数 \(n,m,q\)，意义如题所示。

接下来 \(m\) 行，每行两个整数 \(a,b\)。

接下来 \(q\) 行，每行两个整数 \(k,p\)。

输出格式

对于每一个询问，输出一行表示答案。

样例

输入#1

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

输出#1

2
1
5

数据范围

对于 \(10\%\) 的数据，为样例。

对于 \(20\%\) 的数据，满足 \(n,m,q,k\le 500\)。

对于 \(100\%\) 的数据，满足 \(n,q\le 10^6，m\le 1000，k\le 10^9，a,b,p\le n\)。

wjq温馨提醒：此题输入约15MB，输出约6MB，需要一些卡常

快读模板：

inline int in()
{
    int N=0;
    char ch;
    ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while('0'≤ch&&ch≤'9')
    N=N*10+ch-'0',ch=getchar();
    return N;
}
int main()
{
    a=in();
}