N. How many rectangles?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Doha and Takoo love geometry. Doha wants to give a geometry problem to Takoo and challenges her to solve it.

There are $$$n$$$ rectangles. Doha gives Takoo two coordinate points for each rectangle. The first one is the lower left point $$$(x_{1},y_{1})$$$ and the second one is the upper right point $$$(x_{2},y_{2})$$$. Takoo will record all the coordinates' points, and Doha will ask her $$$Q$$$ queries. In each query, Doha gives her the upper right points of a rectangle that start from the origin. She asks Takoo to count the number of rectangles totally included in this boundary.

For example, given:

  • First rectangle $$$x_{1}$$$,$$$y_{1}$$$ $$$(1,2)$$$ and $$$x_{2}$$$,$$$y_{2}$$$ $$$(7,6)$$$.
  • Second rectangle $$$x_{1}$$$,$$$y_{1}$$$ $$$(7,0)$$$ and $$$x_{2}$$$,$$$y_{2}$$$ $$$(10,3)$$$.
  • Boundary $$$x$$$,$$$y$$$ $$$(8,10)$$$
  • There is one rectangle in this boundary.
Input

The first line of input contains $$$n$$$ $$$(1 \leq n \leq 10^{5})$$$, where $$$n$$$ is the number of rectangles.

The following $$$n$$$ lines contain $$$2D$$$ coordinate points for each rectangle $$$(x_{1}$$$,$$$y_{1})$$$, $$$(x_{2}$$$,$$$y_{2})$$$ $$$(0\leq x_{1} \lt x_{2} \leq 10^{9})$$$ $$$(0\leq y_{1} \lt y_{2} \leq 10^{9})$$$.

The third line of input contains $$$Q$$$ $$$(1 \leq Q \leq 10^{5})$$$ where $$$Q$$$ is the number of queries Doha asks to Taboo.

Each of the next $$$Q$$$ lines contains $$$x$$$ and $$$y$$$ $$$(0\leq x,y \leq 10^{9})$$$ where $$$x$$$, $$$y$$$ are the coordinates of the upper right corner of the query rectangle that starts from the origin.

Output

$$$Q$$$ lines, each line contains the number of rectangles in this boundary.

Example
Input
5
2 3 3 4
4 7 5 8
1 10 4 15
2 5 5 8
4 10 7 12
7
7 5
15 20
6 10
7 11
4 10
3 9
6 8
Output
1
5
3
3
1
1
3