Bob 常常追忆过去。他发现，自己自从认识 Alice，性格改变了很多。
他用 个问题的答案来刻画自己的性格，这些问题的答案均为正整数。
在不认识 Alice 时，他对这些问题的答案依次为 。
后来，Alice 让他的性格发生了 次改变，其中第 次改变让他把问题 的答案改成 。
Bob 问他自己，他该在哪里停留，于是开始追忆过去。他对你进行了 次询问，每次询问都形如“在第 次改变之前，自己对问题 的答案是什么”。你能回答他吗？
输入的第一行有三个正整数 ，分别表示 Bob 考虑的问题个数、改变次数和询问个数。
第二行有 个正整数 ，表示 Bob 一开始对每个问题的答案。
之后有 行，其中的第 行有两个正整数 ，表示第 次改变把问题 的答案改成了 。
之后有 行，每行有两个正整数 ，表示 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 的询问：
【数据范围】
对于全体数据，保证：
本题共 组测试数据，部分测试数据拥有特殊性质，具体地：
