题目描述
有一条由连续排列的 n 个格子组成的木板,格子从左到右编号为 1 到 n。
Alice 和 Bob 分别站在一个格子上,并且始终满足 Alice 所在位置小于 Bob 所在位置(即在 Bob 左边)。
木板上有 m 块跳板,第 i 块跳板安装在位置 xi,使用后会落到位置 yi。同一位置可以有多块跳板,跳板可以被不限次数地使用。
一次动作中,恰好一人进行以下操作之一:
- 行走:
- Alice 向右移动一格;
- Bob 向左移动一格。
- 跳跃:使用当前所在位置的一块跳板,从 xi 跳到 yi。
每次动作后都必须满足 Alice 仍在 Bob 的左侧,否则该动作不能执行。
现在有 Q 个查询。第 j 个查询给出 aj,bj,cj,dj,其中 1≤aj<bj≤n,1≤cj<dj≤n。
判断是否可以通过若干次合法动作,使 Alice 和 Bob 从 (aj,bj) 移动到 (cj,dj)。
对每个查询输出其是否有效。
输入格式
第一行依次给出两个以空格分隔的整数 n 和 m。
接下来的 m 行给出 m 块跳板的信息。其中第 i 行依次给出两个以空格分隔的整数 xi 和 yi,表示第 i 块跳板。
下一行给出查询数量 Q。
接下来的 Q 行给出 Q 个查询的信息。其中第 j 行依次给出四个整数 aj,bj,cj,dj。
输出格式
从第一行开始依次输出 Q 行答案。
第 j 行输出第 j 个查询的答案:若可以将 Alice 和 Bob 从 (aj,bj) 移动到 (cj,dj),输出 YES;否则输出 NO。
样例 1 输入
6 2
3 5
4 2
4
2 4 3 4
2 3 2 5
2 3 4 5
3 4 1 2
样例 1 输出
YES
YES
YES
NO
样例 2 输入
10 3
5 10
6 8
7 4
5
5 6 4 10
5 6 3 9
1 10 2 9
6 8 4 9
9 10 1 10
样例 2 输出
YES
NO
YES
YES
NO
数据范围
对于所有测试数据,保证:
- 2≤n≤200000;
- 0≤m≤200000;
- 1≤Q≤500000;
- 对于每个整数 i,1≤xi,yi≤n 且 xi=yi;
- 对于每个整数 j,1≤aj<bj≤n 且 1≤cj<dj≤n。
| 测试点 |
n,m≤ |
Q≤ |
特殊性质 |
| 1∼4 |
10 |
5 |
无 |
| 5∼8 |
100 |
| 9∼11 |
200000 |
500000 |
∀i≤m,xi<yi |
| 12∼13 |
3000 |
无 |
| 14∼15 |
200000 |
10 |
| 16∼20 |
500000 |