Dây lá cờ

Kỷ niệm \(10/03\) năm nay là ngày lễ lớn, tròn \(50\) năm ngày giải phóng thành phố Buôn Ma Thuột. Thành phố đã trang trí đường Lê Duẩn bằng các dây lá cờ dọc theo tuyến đường. Thảo rất thích ngắm các lá cờ treo dọc đường và nhận ra có đoạn rất nhiều dây lá cờ treo song song nhưng cũng có đoạn không nhiều. Thảo đặt ra bài toán cho các bạn như sau:

Xem con đường là một trục tọa độ \(Ox\). Cho \(N\) (\(N \le 10^6\)) dây lá cờ được đánh số từ \(1\) đến \(N\), dây thứ \(i\) được treo bắt đầu tại tọa độ \(u_i\) đến \(v_i\) (\(1 \le i \le N\), \(0 < u_i \le v_i \le 2 \cdot 10^9\)). Thảo muốn biết tại tọa độ \(x\) (\(0 < x \le 2 \cdot 10^9\)) nào đó có bao nhiêu dây lá cờ được treo.

Yêu cầu: Cho \(Q\) câu hỏi (\(Q \le 10^5\)), câu hỏi thứ \(j\) (\(1 \le j \le Q\)) là một số nguyên \(x_j\). Cho biết tại tọa độ \(x_j\) có bao nhiêu dây lá cờ được treo (dây \(i\) được treo tại \(x_j\) nếu \(u_i \le x_j \le v_i\)).

Input

Dữ liệu vào có cấu trúc:

• Dòng thứ nhất ghi số nguyên dương \(N\).

• Dòng thứ \(i\) trong \(N\) dòng tiếp theo ghi cặp số nguyên dương \(u_i, v_i\).

• Dòng tiếp theo ghi số nguyên dương \(Q\) là số lượng câu hỏi.

• Dòng tiếp theo ghi \(Q\) số nguyên dương \(x_1, x_2, \ldots, x_Q\).
  Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi dấu cách.

Ràng buộc:

• Có \(50\%\) số test tương ứng \(50\%\) số điểm với \(1 \le N \le 10^3\) và \(1 \le u_i, v_i \le 10^3\);

• Có \(30\%\) số test tương ứng \(30\%\) số điểm với \(1 \le N \le 10^6\) và \(1 \le u_i, v_i \le 10^6\);

• Có \(20\%\) số test tương ứng \(20\%\) số điểm không có ràng buộc gì thêm.

Output

In ra \(Q\) dòng, dòng thứ \(j\) là số lượng dây lá cờ được treo tại tọa độ \(x_j\) tương ứng trong dữ liệu vào.

Example

Input:

3
1 7
3 8
4 6
3
2 3 5

Output:

1
2
3

Note

Ba dây được treo trên các đoạn \([1, 7]\), \([3, 8]\), \([4, 6]\). Tại \(x = 2\) có \(1\) dây, tại \(x = 3\) có \(2\) dây, tại \(x = 5\) có \(3\) dây.