Khu đô thị Phú Cường Rạch Giá là điểm check-in sống ảo được nhiều bạn trẻ khám phá khi du lịch Kiên Giang. Điểm đến này ấn tượng bởi không gian kiến trúc sang trọng mang đậm hơi hướng phương Tây. Trong quy hoạch trồng cây xanh nhà đầu tư có ý tưởng như sau:

Cho ~N~ điểm (Tương đương ~N~ cây xanh được trồng) được biểu diễn trên trục Ox, các điểm được đánh số lần lượt từ 1 đến ~N~.

Cho ~M~ thao tác mỗi thao tác sẽ có dạng: Gồm một số nguyên ~k~, yêu cầu cần đổi vị trí của tất cả các điểm trong ~N~ điểm trên trục Ox thành vị trí đối xứng của nó với đường thẳng ~x = k~.

Cho ~Q~ truy vấn, mỗi truy vấn sẽ có dạng: Gồm 2 số nguyên ~id~ và ~K~. Với mỗi truy vấn yêu cầu in ra vị trí của điểm thứ ~id~ sau ~K~ thao tác.

Yêu cầu: Tính vị trí của các điểm sau các thao tác và truy vấn.

Input

• Dòng đầu tiên chứa 3 số nguyên ~N, M, Q~.
• Tiếp theo là ~N~ số nguyên ~x[i]~ với ~x[i]~ là vị trí của điểm thứ ~i~ (~|x[i]| \le 10^9~).
• Tiếp theo là ~M~ dòng, dòng thứ ~i~ có số nguyên ~k~ thể hiện cho thao tác thứ ~i~.
• Tiếp theo là ~Q~ dòng, dòng thứ ~i~ gồm 2 số nguyên ~id, K~ thể hiện cho truy vấn thứ ~i~ (~id \le N, K \le M~).

Output

• Gồm ~Q~ dòng, với mỗi truy vấn, in ra đáp án cho truy vấn đó.

Sample Input 1

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

Sample Output 1

2
6
-4
8
3