B4526 [语言月赛 202604] 追忆？

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 的一次询问。

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

【样例 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$。