Bán hàng qua mạng

Bán hàng qua mạng là một hình thức kinh doanh ngày càng phổ biến. Để thực hiện được việc bán hàng qua mạng, nhà sản xuất thông qua một phần mềm giới thiệu các sản phẩm, khách hàng sử dụng phần mềm này để lựa chọn sản phẩm cần mua. Phần mềm giới thiệu có nhiều loại sản phẩm, mỗi sản phẩm có nhiều thông số, trong đó hai thông số cơ bản là giá bán và số khách hàng đã mua.

Khách hàng lựa chọn loại sản phẩm cần mua và cung cấp hai số nguyên \(x, y\) (\(x \le y\)) là khoảng giá cần mua của loại sản phẩm đó. Trong mỗi khoảng giá, phần mềm sẽ đưa ra sản phẩm có nhiều khách hàng mua nhất.

Yêu cầu: Cho \(n\) sản phẩm và \(Q\) yêu cầu của khách hàng. Với mỗi yêu cầu hãy đưa ra số khách hàng đã mua nhiều nhất của sản phẩm có giá trong khoảng đó.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 10^5\)).

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo (\(1 \le i \le n\)), mỗi dòng có \(2\) số nguyên dương \(v_i\) và \(s_i\) (\(1 \le v_i, s_i \le 10^9\)) cách nhau một dấu cách. Trong đó \(v_i\) là giá bán và \(s_i\) là số khách hàng đã mua sản phẩm thứ \(i\).

• Dòng thứ \(n+2\) chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^5\)).

• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(x, y\) (\(1 \le x \le y \le 10^9\)) là khoảng giá mà khách hàng đưa ra.

Ràng buộc:

• Có \(70\%\) số test ứng với \(70\%\) số điểm của bài thỏa mãn điều kiện: \(Q, n \le 10^3\).

• \(30\%\) số test còn lại ứng với \(30\%\) số điểm không có ràng buộc gì thêm.

Output

Gồm \(Q\) dòng, mỗi dòng tương ứng với một yêu cầu, chỉ cần in ra một số nguyên là số khách hàng đã mua nhiều nhất của sản phẩm tìm được. Nếu không có sản phẩm nào trong khoảng giá thì in ra \(0\).

Example

Input:

2
2 3
5 8
3
6 8
1 3
1 6

Output:

0
3
8

Note

Có hai sản phẩm: giá \(2\) có \(3\) khách hàng, giá \(5\) có \(8\) khách hàng. Khoảng giá \([6, 8]\) không có sản phẩm nào nên in \(0\); khoảng \([1, 3]\) chỉ chứa sản phẩm giá \(2\) nên in \(3\); khoảng \([1, 6]\) chứa cả hai sản phẩm nên in \(\max(3, 8) = 8\).