题目背景

滥用本题评测将封号！

题目描述

给定一个平面，有 $n$ 个竖直线段，第 $i$ 条的端点是 $(i,a_i)$ 和 $(i,b_i)$。

有 $m$ 次查询，每次查询给定 $l,r,x,y$，查询对所有 $(x,i)$ 和 $(y,i)$ 连接成的水平线段，满足 $l\le i\le r$，其最多能与多少竖直线段相交，定义端点为 $(i,a_1)$ 和 $(i,a_2)$ 的竖直线段与端点为 $(b_1,j)$ 和 $(b_2,j)$ 的水平线段相交，当且仅当 $a_1\le j\le a_2$ 且 $b_1\le i\le b_2$，注意当线段两端点重合时，如果有其他线段经过这个重合点，仍然算作相交。

输入格式

第一行一个数表示 $n$。

之后 $n$ 行，第 $i$ 行两个数 $a_i,b_i$ 表示 第 $i$ 条竖直线段的两个端点，保证 $a_i \le b_i$。

之后一行一个数表示 $m$。

之后 $m$ 行，每行四个数表示一次询问的 $l,r,x,y$。

输出格式

对于每次询问，输出一行一个数表示答案。

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

提示

注意：本题采用捆绑测试，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于 $100\%$ 的数据，$1\le n\le 5\times 10^5,1\le m\le 9\times 10^5$，$1\le l,r,x,y,a_i,b_i\le n$。

以下为旧数据范围

对于其中 $5\%$ 的数据，为样例 1。

对于另外 $14\%$ 的数据，$m=1$。

对于另外 $5\%$ 的数据，$n,m\leq 500$。

对于另外 $14\%$ 的数据，$n\leq 500$。

对于另外 $19\%$ 的数据，$n,m\leq 2000$。

对于另外 $19\%$ 的数据，$n\leq 20000$。

对于 $100\%$ 的数据，$1\le n\le 5\times 10^4,1\le m\le 5\times 10^5$，$1\le l,r,x,y,a_i,b_i\le n$。