Có ~n~ loại kẹo. Loại thứ ~i~ có ~a_i~ viên kẹo, mỗi viên nặng ~w_i~. Không có hai loại kẹo nào có cùng khối lượng.

Toàn bộ số kẹo được đổ ra bàn và xếp thành một hàng sao cho khối lượng của chúng tạo thành một dãy không giảm. Cho ~q~ truy vấn, hãy cho biết viên kẹo thứ ~k~ trên bàn nặng bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i~ và ~w_i~.
• ~q~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~k~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

3 3
2 2
1 1
3 3
1
3
5

Đầu ra:

1
2
3

Giải thích: Hàng kẹo trên bàn là ~1, 2, 2, 3, 3, 3~. Viên thứ ~1~ nặng ~1~, viên thứ ~3~ nặng ~2~, viên thứ ~5~ nặng ~3~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le a_i, w_i \le 10^9~
• ~1 \le k \le a_1 + a_2 + \ldots + a_n \le 10^{14}~

Các khối lượng ~w_i~ đôi một khác nhau. Tổng số kẹo lên tới ~10^{14}~ nên ~k~ không vừa trong số nguyên 32 bit.