Description

Given a plane with $n$ vertical line segments. The $i$-th segment has endpoints $(i,a_i)$ and $(i,b_i)$.

There are $m$ queries. Each query gives $l,r,x,y$. Consider all horizontal segments connecting $(x,i)$ and $(y,i)$ for $l\le i\le r$. For these horizontal segments, ask what is the maximum number of vertical segments that a segment can intersect.

A vertical segment with endpoints $(i,a_1)$ and $(i,a_2)$ intersects a horizontal segment with endpoints $(b_1,j)$ and $(b_2,j)$ if and only if $a_1\le j\le a_2$ and $b_1\le i\le b_2$. Note that when two segments share an endpoint, if other segments pass through this shared point, it is still counted as an intersection.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $a_i,b_i$, representing the two endpoints of the $i$-th vertical segment. It is guaranteed that $a_i \le b_i$.

Then a line contains an integer $m$.

The next $m$ lines each contain four integers, representing one query: $l,r,x,y$.

Output Format

For each query, output one line with one integer, representing the answer.

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

2
3
4
3
7
7
1
2
2
2

Hint

Note: This problem uses bundled testdata. You can only get the score for a subtask after you pass all test points in that subtask.

For $100\%$ of the data, $1\le n\le 5\times 10^5$, $1\le m\le 9\times 10^5$, and $1\le l,r,x,y,a_i,b_i\le n$.

Below are the old Constraints

For $5\%$ of the data, it is Sample 1.

For another $14\%$ of the data, $m=1$.

For another $5\%$ of the data, $n,m\leq 500$.

For another $14\%$ of the data, $n\leq 500$.

For another $19\%$ of the data, $n,m\leq 2000$.

For another $19\%$ of the data, $n\leq 20000$.

For $100\%$ of the data, $1\le n\le 5\times 10^4$, $1\le m\le 5\times 10^5$, and $1\le l,r,x,y,a_i,b_i\le n$.

Translated by ChatGPT 5