题目描述

Bob 常常追忆过去。他发现，自己自从认识 Alice，性格改变了很多。

他用 $n$ 个问题的答案来刻画自己的性格，这些问题的答案均为正整数。

在不认识 Alice 时，他对这些问题的答案依次为 $a_1,\ldots,a_n$。

后来，Alice 让他的性格发生了 $m$ 次改变，其中第 $i$ 次改变让他把问题 $x_i$ 的答案改成 $y_i$。

Bob 问他自己，他该在哪里停留，于是开始追忆过去。他对你进行了 $q$ 次询问，每次询问都形如“在第 $u$ 次改变之前，自己对问题 $v$ 的答案是什么”。你能回答他吗？

输入格式

输入的第一行有三个正整数 $n,m,q$，分别表示 Bob 考虑的问题个数、改变次数和询问个数。

第二行有 $n$ 个正整数 $a_1,\ldots,a_n$，表示 Bob 一开始对每个问题的答案。

之后有 $m$ 行，其中的第 $i$ 行有两个正整数 $x_i,y_i$，表示第 $i$ 次改变把问题 $x_i$ 的答案改成了 $y_i$。

之后有 $q$ 行，每行有两个正整数 $u,v$，表示 Bob 的一次询问。

输出格式

对于每次询问，输出一行一个正整数，表示询问的答案。

4 4 5
10 20 30 40
1 50
3 60
1 70
1 80
1 1
2 1
3 1
4 1
3 2

10
50
50
70
20

提示

【样例 1 解释】

• 初始时，Bob 的性格为 $(10,20,30,40)$。（即第 $1$ 个问题的答案为 $10$，以此类推）。
• 第 $1$ 次改变后，他的性格为 $(50,20,30,40)$。
• 第 $2$ 次改变后，他的性格为 $(50,20,60,40)$。
• 第 $3$ 次改变后，他的性格为 $(70,20,60,40)$。
• 第 $4$ 次改变后，他的性格为 $(80,20,60,40)$。

接下来你将会回答 Bob 的询问：

• 第 $1$ 次改变前（也就是初始时），他对问题 $1$ 的答案为 $10$。
• 第 $2$ 次改变前（也就是第 $1$ 次改变后），他对问题 $1$ 的答案为 $50$。
• 第 $3$ 次改变前（也就是第 $2$ 次改变后），他对问题 $1$ 的答案为 $50$。
• 第 $4$ 次改变前（也就是第 $3$ 次改变后），他对问题 $1$ 的答案为 $70$。
• 第 $3$ 次改变前（也就是第 $2$ 次改变后），他对问题 $2$ 的答案为 $20$。

【数据范围】

对于全体数据，保证：

• $1\le n\le 50$，$1\le m,q\le 50000$。
• $1\le x_i\le n$，任意时刻 $1\le a_i\le 10^9$（即十亿）。
• 对于任意询问有 $1\le u\le m$，$1\le v\le n$。

本题共 $10$ 组测试数据，部分测试数据拥有特殊性质，具体地：

• 测试点 $1,2$ 保证 $n=1$。
• 测试点 $3,4$ 保证 $m=1$。
• 测试点 $1\sim 7$ 保证 $m,q\le 100$。