P7290 "EZEC-5" Brute Force Creates Miracles

### Abusing this problem’s judging system will result in your account being banned!

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.

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$.

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

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