Vương quốc JOI có một con đường thẳng rất dài chạy theo hướng đông-tây. Cung điện ở vị trí \(0\); vị trí \(A>0\) cách cung điện \(A\) mét về phía đông, còn \(A<0\) cách cung điện \(-A\) mét về phía tây.

Có \(N\) ngôi nhà, đánh số từ tây sang đông. Nhà \(i\) ở tọa độ chẵn khác \(0\) là \(A_i\), và mọi \(A_i\) đôi một khác nhau. Công dân \(i\) sống tại nhà \(i\).

Theo lệnh nhà vua, mọi công dân đồng thời bắt đầu đi về đông hoặc tây theo hướng đã định, với vận tốc 1 mét mỗi giây. Khi gặp một công dân khác, kể cả một người đã dừng, họ dừng tại đó để trò chuyện và không bao giờ đi tiếp.

Nhà vua muốn biết vị trí của \(Q\) nhân vật quan trọng sau \(T\) giây.

Dữ liệu vào

• Dòng đầu chứa \(N,T,Q\), với \(1\le N\le10^5\), \(0\le T\le10^{18}\) và \(1\le Q\le\min(N,1000)\).
• \(N\) dòng tiếp theo: dòng \(i\) chứa \(A_i,D_i\). Ta có \(-10^{18}\le A_i\le10^{18}\); \(A_i\) là số chẵn khác \(0\); \(A_i<A_{i+1}\); \(D_i=1\) nghĩa là đi về đông và \(D_i=2\) nghĩa là đi về tây.
• \(Q\) dòng cuối: dòng \(i\) chứa \(X_i\) (\(1\le X_i\le N\)), là chỉ số nhân vật quan trọng thứ \(i\); \(X_i<X_{i+1}\).

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(i\) là vị trí của nhân vật quan trọng thứ \(i\) sau \(T\) giây. Các điều kiện của đề bảo đảm vị trí này là số nguyên.

Chấm điểm

Có 5 bộ dữ liệu, mỗi bộ trị giá 20 điểm:

• Dữ liệu 1: \(N\le100\), \(T\le10000\).
• Dữ liệu 2: \(N\le5000\).
• Dữ liệu 3: tồn tại \(M\) (\(1\le M\le N-1\)) sao cho \(D_i=1\) với \(1\le i\le M\) và \(D_j=2\) với \(M+1\le j\le N\).
• Trong dữ liệu 1, 2, 3, trị tuyệt đối của mọi số nguyên trong dữ liệu vào không vượt quá \(10^9\).
• Dữ liệu 4, 5 không có ràng buộc bổ sung; các số có thể không nằm trong miền số nguyên có dấu 32 bit.

Ví dụ

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

-6
-6
15

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

-82
-16
-13
-13
0

Nguồn

Kỳ thi sơ loại Olympic Tin học Nhật Bản 2015/2016, bài 4.