Tiến là một công nhân làm việc ở nhà máy socola QH. Công việc của anh là điều chỉnh nhiệt độ của hồ nhiệt độ. Hôm nay anh nhận được một đơn đặt hàng rất lớn đến từ Khoa. Vì là đơn đặt hàng rất lớn nên nhà máy đã đưa ra một quy trình để chuẩn hóa nhiệt độ như sau:

Cho hai dãy số nguyên độ dài ~N~ ~(N \leq 10^5)~:

• Dãy ~A~ gồm ~N~ số nguyên ~A = (a_1, a_2, a_3, \dots, a_N)~ ~(|a_i| \leq 10^9)~.
• Dãy ~T~ gồm ~N~ số nguyên ~T = (t_1, t_2, t_3, \dots, t_N)~ ~(1 \leq t_i \leq 3)~.

Quy trình chuẩn hóa sẽ gồm ~N~ bước, ở bước thứ ~i~ bạn cần phải:

• Với ~t_i = 1~ thì bạn cần tăng nhiệt độ của hồ nhiệt lên ~a_i~ đơn vị nhiệt độ.
• Với ~t_i = 2~, nếu nhiệt độ hồ nhiệt lớn hơn ~a_i~ thì bạn không làm gì cả, ngược lại thì thay đổi nhiệt độ hồ nhiệt thành ~a_i~.
• Với ~t_i = 3~, nếu nhiệt độ hồ nhiệt nhỏ hơn ~a_i~ thì bạn không làm gì cả, ngược lại thì thay đổi nhiệt độ hồ nhiệt thành ~a_i~.

Vì là đơn hàng rất lớn nên Tiến không thể để xảy ra bất kỳ sai sót nào. Tiến đã đặt ra ~Q~ ~(Q \leq 10^5)~ tình huống giả định, hỏi rằng nếu nhiệt độ ban đầu của hồ nhiệt là ~x_i~ ~(|x_i| \leq 10^9)~ thì sau ~N~ bước chuẩn hóa, nhiệt độ cuối cùng của hồ nhiệt sẽ là bao nhiêu?

Bạn hãy giúp Tiến thực hiện nhiệm vụ quan trọng này.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ là số bước trong quy trình chuẩn hóa.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa cặp số nguyên ~a_i, t_i~.
• Dòng tiếp theo chứa số nguyên dương ~Q~ là số tình huống giả định mà bạn cần phải trả lời.
• Dòng tiếp theo chứa dãy số ~X = (x_1, x_2, x_3, \dots, x_Q)~ độ dài ~Q~ lần lượt là nhiệt độ ban đầu của hồ nhiệt trong các tình huống giả định.

Output

Bạn cần ghi ra ~Q~ dòng.

• Dòng thứ ~i~ chứa nhiệt độ của hồ nhiệt sau khi thực hiện xong ~N~ bước nếu nhiệt độ ban đầu là ~x_i~.

Subtask

• Subtask ~1~ (~10\%~ số điểm): ~Q = 1~.
• Subtask ~2~ (~10\%~ số điểm): ~N, Q \leq 5000~.
• Subtask ~3~ (~30\%~ số điểm): ~t_i \neq 1~.
• Subtask ~4~ (~50\%~ số điểm): không có giới hạn gì thêm.

Sample Input

3
-10 2
10 1
10 3
5
-15 -10 -5 0 5

Sample Output

0
0
5
10
10

Note

Ở tình huống giả định đầu tiên, nhiệt độ ban đầu là ~-15~ đơn vị nhiệt độ. Quy trình chuẩn hóa sẽ diễn ra như sau:

• Ở bước đầu tiên, ~t_1 = 2~ và ~a_1 = -10~, vì ~-15 < -10~ nên nhiệt độ của hồ nhiệt trở thành ~-10~.
• Ở bước thứ hai, ~t_2 = 1~ và ~a_2 = 10~, nhiệt độ của hồ nhiệt sẽ được tăng ~10~ đơn vị nhiệt độ và hồ nhiệt độ sẽ có nhiệt độ là ~0~.
• Ở bước cuối cùng, ~t_3=3~ và ~a_3=10~, vì ~0 < 10~ nên nhiệt độ của hồ nhiệt vẫn giữ nguyên là ~0~.

Sau khi hoàn thành quy trình chuẩn hóa thì nhiệt độ của hồ nhiệt là ~0~.