Ở vương quốc JOI, có $1$ con đường đủ dài chạy theo hướng đông - tây. Cung điện hoàng gia của vương quốc JOI nằm dọc theo con đường, và một vị trí dọc theo con đường ở vương quốc JOI được biểu thị bằng một số nguyên $A$. Khi $A = 0$, nó biểu thị vị trí của cung điện hoàng gia. Khi $A > 0$, nó biểu thị vị trí cách cung điện hoàng gia $A$ mét về phía đông. Khi $A < 0$, nó biểu thị vị trí cách cung điện hoàng gia $-A$ mét về phía tây.

Có $N$ ngôi nhà dọc theo con đường ở vương quốc JOI, được đánh số từ $1$ đến $N$ theo thứ tự từ tây sang đông. Có $N$ công dân ở vương quốc JOI, được đánh số từ $1$ đến $N$. Công dân $i$ sống ở ngôi nhà $i$. Vị trí của ngôi nhà $i$ được biểu thị bằng một số nguyên chẵn khác $0$ là $A_i$. Tất cả $A_1, \dots, A_N$ đều đôi một khác nhau.

Ở vương quốc JOI, tình trạng thiếu vận động của công dân gần đây đã trở thành một vấn đề. Lo lắng cho sức khỏe của người dân, Nhà vua của vương quốc JOI đã ban lệnh cho toàn thể công dân đi dạo. Khi Nhà vua ban lệnh, tất cả công dân đồng loạt bắt đầu đi bộ về hướng đông hoặc hướng tây. Hướng đi bộ của mỗi công dân được quy định sẵn cho từng người. Tất cả công dân khi đi bộ đều đi với vận tốc $1$ mét mỗi $1$ giây.

Mọi công dân của vương quốc JOI đều rất thích trò chuyện. Nếu gặp một công dân khác trên đường đi dạo, họ sẽ dừng lại ngay tại vị trí đó và bắt đầu tán gẫu. Điều tương tự cũng xảy ra nếu họ gặp một công dân đã dừng lại từ trước. Một khi công dân đã dừng lại, họ sẽ không bao giờ bước đi tiếp nữa.

Ở vương quốc JOI có $Q$ nhân vật quan trọng. Nhà vua của vương quốc JOI muốn nắm được vị trí của $Q$ nhân vật quan trọng này sau $T$ giây kể từ khi lệnh được ban ra. Hãy viết chương trình tìm vị trí của $Q$ nhân vật quan trọng sau $T$ giây kể từ khi lệnh được ban ra.

Dữ liệu vào

Dữ liệu vào gồm $1 + N + Q$ dòng.

Ở dòng thứ $1$, có $3$ số nguyên $N, T, Q$ ($1 \le N \le 100000 (= 10^5), 0 \le T \le 10^{18}, 1 \le Q \le 1000, 1 \le Q \le N$) được viết cách nhau bởi khoảng trắng. Điều này biểu thị rằng có $N$ ngôi nhà ở vương quốc JOI, và Nhà vua muốn nắm được vị trí của $Q$ nhân vật quan trọng sau $T$ giây kể từ khi ban lệnh.

Ở dòng thứ $i$ trong $N$ dòng tiếp theo, có $2$ số nguyên $A_i, D_i$ ($-10^{18} \le A_i \le 10^{18}$, $A_i$ là số chẵn khác $0$, $1 \le D_i \le 2$) được viết cách nhau bởi khoảng trắng. $A_i$ là số chẵn biểu thị vị trí của ngôi nhà $i$. Với mọi $i$ ($1 \le i \le N - 1$), điều kiện $A_i < A_{i+1}$ được thỏa mãn. $D_i$ biểu thị hướng mà công dân $i$ bắt đầu đi bộ sau khi lệnh được ban ra. Khi $D_i = 1$, công dân $i$ bắt đầu đi về hướng đông. Khi $D_i = 2$, công dân $i$ bắt đầu đi về hướng tây.

Ở dòng thứ $i$ trong $Q$ dòng tiếp theo, có ghi số nguyên $X_i$ ($1 \le X_i \le N$). Điều này biểu thị rằng nhân vật quan trọng thứ $i$ sống ở ngôi nhà $X_i$. Với mọi $i$ ($1 \le i \le Q - 1$), điều kiện $X_i < X_{i+1}$ được thỏa mãn.

Trong $5$ bộ dữ liệu vào được cho, dữ liệu vào $1$ thỏa mãn $N \le 100, T \le 10000$. Ngoài ra, dữ liệu vào $2$ thỏa mãn $N \le 5000$. Ngoài ra, ở dữ liệu vào $3$, tồn tại một số nguyên $M$ ($1 \le M \le N - 1$) sao cho với mọi $i$ ($1 \le i \le M$) thì $D_i = 1$, và với mọi $j$ ($M + 1 \le j \le N$) thì $D_j = 2$. Hơn nữa, ở các dữ liệu vào $1, 2, 3$, giá trị tuyệt đối của các số nguyên trong dữ liệu vào không vượt quá $1000000000 (= 10^9)$. Lưu ý rằng ở dữ liệu vào $4, 5$, các số nguyên được cho có thể không nằm trong phạm vi của số nguyên có dấu $32$-bit.

Dữ liệu ra

Dữ liệu ra gồm $Q$ dòng.

Ở dòng thứ $i$ ($1 \le i \le Q$), hãy in ra số nguyên biểu thị vị trí của nhân vật quan trọng thứ $i$ sau $T$ giây kể từ khi Nhà vua ban lệnh. Các điều kiện trong đề bài đảm bảo rằng giá trị này luôn là một số nguyên.

Ví dụ

Dữ liệu vào 1

5 5 3
-8 1
-4 2
-2 2
4 2
10 1
1
3
5

Dữ liệu ra 1

-6
-6
15

Dữ liệu vào 2

7 18 5
-100 1
-56 2
-34 1
-30 1
-22 1
-4 2
18 2
1
3
4
5
7

Dữ liệu ra 2

-82
-16
-13
-13
0