Miền Tây hoang dã tại nước Mỹ xa xôi sắp diễn ra một cuộc thi đấu giữa những chàng cao bồi tài hoa. \(m\) chàng cao bồi phải đi tìm kiếm cho mình những chú ngựa cừ khôi như là một phần của cuộc thi.

Biết rằng mảnh đất viễn tây có thể biểu diễn dưới dạng toạ độ \(Oxy\). Cụ thể, bốn điểm \((x, y)\), \((x - 1, y)\), \((x, y - 1)\), \((x - 1, y - 1)\) sẽ tạo ra một ô vuông đơn vị. Tại một số ô vuông đơn vị sẽ có những chú ngựa đang say sưa tắm nắng. Các chàng cao bồi sẽ lần lượt chọn ra một điểm có toạ độ \((u, v)\) và thực hiện:

• Từ điểm \((u, v)\) tạo hàng rào sang trái song song với trục \(Ox\) và hàng rào xuống dưới song song với trục \(Oy\) cho đến khi chạm vào một trong hai trục hoặc một hàng rào trước đó. Cuộc thi đảm bảo toạ độ không có hai chàng cao bồi nào chọn cùng toạ độ \(u\) hoặc cùng toạ độ \(v\).
• Chàng cao bồi sẽ thu thập hết tất cả con ngựa trong mảnh đất được giới hạn bởi hàng rào từ các chàng cao bồi trước đó, hai trục \(Ox, Oy\) và hàng rào của mình vừa tạo.

Hãy tính số con ngựa mà mỗi chàng cao bồi thu thập được để ban tổ chức có thể tìm ra người chiến thắng.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 3 \cdot 10^{5})\) là số lượng con ngựa.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_{i}\) và \(y_{i}\) \((1 \leq x_{i}, y_{i} \leq 10^{9})\) là tọa độ góc phải trên của ô vuông đơn vị của con ngựa thứ \(i\).
• Dòng tiếp theo chứa số nguyên \(m\) \((1 \leq m \leq 3 \cdot 10^{5})\) là số lượng chàng cao bồi tham gia cuộc thi.
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i}, v_{i} \leq 10^{9})\) là tọa độ mà chàng cao bồi thứ \(i\) chọn.

Output

• In ra \(m\) dòng, dòng thứ \(i\) chứa một số nguyên là số con ngựa mà chàng cao bồi thứ \(i\) thu thập được.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(x_{1} = x_{2} = \ldots = x_{n}\) hoặc \(y_{1} = y_{2} = \ldots = y_{n}\).
• Subtask \(2\) (\(30\%\) số điểm): \(n, m \leq 2 \cdot 10^{3}\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 2
1 3
1 4
1 5
1 6
5
6 7
5 6
4 5
3 3
8 4

5
5
4
2
0

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

10
9
6
3
1