Dũng rất thích sưu tầm heo đất và nuôi chúng. Để có đủ tiền để đi tham quan các địa điểm du lịch nỗi tiếng của Ninh Bình trong đợt thi DH và ĐBBB 2017, Dũng sưu tầm được \(N\) con heo đất và đánh số từ \(1\) đến \(N\), ban đầu chúng đều rỗng. Mỗi ngày cậu ta chọn ra 1 cặp \((L,R)\) và bỏ vào mỗi heo đất trong đoạn có chỉ số từ \(L\) đến \(R\) 1 đồng tiền. Cậu ta thực hiện như vậy trong \(M\) ngày.

Yêu cầu: Sau \(M\) ngày, Dũng muốn biết có bao nhiêu tiền trong mỗi hộp đựng tiền.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N,M\) (\(N\): số hộp tiền, \(M\): số ngày mà Dũng thực hiện).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L\) và \(R\).
• Dòng thứ \(M+2\) chứa một số nguyên \(Q\) là số lượng truy vấn.
• \(Q\) dòng tiếp theo chứa một số nguyên dương \(x\) \((x \le M)\) của từng truy vấn.

Output

• Ghi ra gồm \(N\) số nguyên là số lượng tiền có trong \(N\) hộp chứa tiền.

Scoring

• Có \(30\%\) số test ứng với 30% số điểm có \(N,M,Q \le 10^2\).
• Có \(30\%\) số test ứng với 30% số điểm có \(N,M,Q \le 10^4\).
• Có \(40\%\) số test ứng với 40% số điểm có \(N,M,Q \le 10^5\).

Example

7 4
1 3
2 5
1 2
5 6

2 3 2 1 2 1 0