Sau một chuyến du lịch liên hành tinh, thầy Nam trở về từ hành tinh An Bình. Điểm đặc biệt của hành tinh này là một ngày có đúng ~M~ giờ. Thầy Nam mua ~N~ chiếc đồng hồ chưa được chỉnh giờ ở An Bình. Mỗi đồng hồ có một màn hình hiển thị giờ hiện tại bằng một số từ ~0~ đến ~M-1~.

Các đồng hồ này không hoạt động mãi mãi: đồng hồ thứ ~i~ hoạt động đúng ~a_i~ giờ rồi dừng hẳn và không hiển thị gì nữa. Tại thời điểm mua, đồng hồ thứ ~i~ đang bắt đầu hiển thị giờ ~b_i~. Ví dụ, nếu ~M=7~ và một đồng hồ đang bắt đầu hiển thị giờ ~b_i=5~ lúc mua, đồng thời còn hoạt động trong ~a_i=4~ giờ, thì đồng hồ đó lần lượt hiển thị các giờ ~5, 6, 0, 1~, sau đó dừng hoạt động.

Thầy Nam muốn trả lời ~Q~ truy vấn. Mỗi truy vấn được cho bởi một số ~t_i~; với truy vấn này, cần tính tổng ~s_1 + \dots + s_N~, trong đó ~s_j~ là số lần màn hình của đồng hồ thứ ~j~ hiển thị giờ ~t_i~ trước khi đồng hồ đó dừng hoạt động.

Hãy giúp thầy Nam trả lời tất cả các truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(1 \le N \le 2 \cdot 10^5, 1 \le M \le 10^9)~: số đồng hồ và số giờ trong một ngày ở hành tinh An Bình.

• Trong ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i \le 10^{12}, 0 \le b_i < M)~: số giờ đồng hồ thứ ~i~ còn hoạt động và giờ mà đồng hồ đó hiển thị tại thời điểm mua.

• Dòng tiếp theo chứa một số nguyên ~Q~ ~(1 \le Q \le 2 \cdot 10^5)~: số truy vấn.

• Trong ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên ~t_i~ ~(0 \le t_i < M)~.

Output

Ghi ra ~Q~ dòng, dòng thứ ~i~ là câu trả lời cho truy vấn thứ ~i~.

Scoring

Sample Input 1

6 8
10 6
5 3
16 2
1 0
9 7
4 5
8
0
1
2
3
4
5
6
7

Sample Output 1

6
4
4
5
5
6
7
8

Notes

• Đồng hồ thứ nhất lần lượt hiển thị các giờ ~6, 7, 0, 1, 2, 3, 4, 5, 6, 7~.

• Đồng hồ thứ ba hoạt động đúng ~16~ giờ, tức là đi qua trọn vẹn hai ngày ở An Bình, nên đóng góp ~2~ lần cho mỗi giờ từ ~0~ đến ~7~.

• Khi cộng đóng góp của tất cả đồng hồ, số lần xuất hiện của các giờ ~0, 1, 2, 3, 4, 5, 6, 7~ lần lượt là ~6, 4, 4, 5, 5, 6, 7, 8~.

• Vì các truy vấn trong ví dụ lần lượt hỏi các giờ từ ~0~ đến ~7~, kết quả chính là các số trên theo đúng thứ tự.