THỰC HÀNH

(Đề đề xuất DHBB 2017 của THPT CHUYÊN LÊ QUÝ ĐÔN -  ĐÀ NẴNG)

Dũng rất thích đi du lịch, vì vậy cậu đã thực hành tiết kiệm tiền để đi du lịch bằng cách nuôi heo đất. Dũng mua N con heo đất (đánh số từ 1 đến N, tất nhiên lúc mới mua về tất cả đầu rỗng) và tiến hành tiết kiệm trong M ngày, mỗi ngày cậu chọn ra một đoạn L, R và bỏ vào mỗi con heo được đánh số thứ tự trong đoạn từ L đến R một đồng tiền. Sau M ngày tiết kiệm, Dũng muốn biết số lượng tiền trong mỗi con heo mình đã nuôi nên cậu đặt ra Q câu hỏi (truy vấn), mỗi câu hỏi, Dũng chọn một số nguyên X và muốn biết có bao nhiêu con heo đất có số lượng ít nhất X đồng tiền?

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên N và M được ghi cách nhau một dấu cách.
• M dòng tiếp theo, mỗi dòng ghi hai số nguyên dương L và R cách nhau một dấu cách.
• Dòng tiếp theo (dòng thứ M + 2) ghi số nguyên dương Q.
• Q dòng tiếp theo, mỗi dòng chứa một số nguyên dương X.

Dữ liệu ra:

            Gồm Q dòng, dòng thứ i ghi một số nguyên là câu trả lời cho câu hỏi thứ i.

Ví dụ:

Dữ liệu vào:
7 4
1 3
2 5
1 2
5 6
4
1
7
4
2
Dữ liệu ra:
6
0
0
4

Giới hạn: 1 ≤ N, M, Q ≤ 10⁵; 1 ≤ L ≤ R ≤ N.