题目描述

Alice 和 Bob 两位杂技演员准备在一条平均木上进行表演。平均木由连续排列的 $N$ 个格子组成，从左到右依次编号为 $1$ 到 $N$。

表演过程中，两位杂技演员在任意时刻都必须分别站在恰好一个格子上。为了保证安全，在表演的任何时刻，Alice 所在格子的编号都必须小于 Bob 所在格子的编号。也就是说，Alice 必须始终站在 Bob 左侧的格子上，且两人不能站在同一个格子上。

平均木上安装了 $M$ 块跳板。第 $i$（$1 \le i \le M$）块跳板安装在第 $x_i$ 个格子上；站在第 $x_i$ 个格子上的杂技演员使用该跳板后，会恰好落在第 $y_i$ 个格子上。

同一个格子上可以安装多块跳板，两位杂技演员也都可以不限次数地使用任意跳板。

一场表演由依次执行任意次动作（也可以执行 $0$ 次）组成。一次动作中，两位杂技演员中的恰好一人执行以下两种操作之一：

1. 行走：Alice 可以从自己所在的格子向右移动一格；Bob 可以从自己所在的格子向左移动一格。Alice 不能向左走，Bob 也不能向右走。
2. 跳跃：选择并使用一块安装在自己所在格子上的跳板。也就是说，对于某个整数 $i$（$1 \le i \le M$），站在第 $x_i$ 个格子上的杂技演员可以使用第 $i$ 块跳板，落到第 $y_i$ 个格子上。

执行动作后，Alice 仍必须站在 Bob 左侧的格子上。会违反这一条件的动作不能执行。

两位杂技演员有 $Q$ 个表演计划。第 $j$（$1 \le j \le Q$）个表演计划由满足 $1 \le a_j<b_j \le N$ 且 $1 \le c_j<d_j \le N$ 的四个整数 $a_j,b_j,c_j,d_j$ 表示。若能通过适当执行若干动作，使 Alice 和 Bob 从分别站在第 $a_j$、第 $b_j$ 个格子的状态开始，最终分别站在第 $c_j$、第 $d_j$ 个格子上，则称第 $j$ 个表演计划有效。

请对 $Q$ 个表演计划逐一判断其是否有效。

输入格式

第一行依次给出两个以空格分隔的整数 $N$ 和 $M$。

接下来的 $M$ 行给出 $M$ 块跳板的信息。其中第 $i$（$1 \le i \le M$）行依次给出两个以空格分隔的整数 $x_i$ 和 $y_i$，表示第 $i$ 块跳板。

下一行给出表示表演计划数量的整数 $Q$。

接下来的 $Q$ 行给出 $Q$ 个表演计划的信息。其中第 $j$（$1 \le j \le Q$）行依次给出四个以空格分隔的整数 $a_j,b_j,c_j,d_j$，表示第 $j$ 个表演计划。

输出格式

从第一行开始依次输出 $Q$ 行答案。第 $j$（$1 \le j \le Q$）行输出第 $j$ 个表演计划的答案：如果能使 Alice 和 Bob 从分别站在第 $a_j$、第 $b_j$ 个格子的状态开始，最终分别站在第 $c_j$、第 $d_j$ 个格子上，则输出 YES；否则输出 NO。

6 2
3 5
4 2
4
2 4 3 4
2 3 2 5
2 3 4 5
3 4 1 2

YES
YES
YES
NO

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

YES
NO
YES
YES
NO

提示

样例 1 解释

在第二个表演计划中，Alice 和 Bob 分别从第 $2$、第 $3$ 个格子开始。Bob 使用第 $3$ 个格子上的跳板移动到第 $5$ 个格子后，Alice 和 Bob 就分别位于第 $2$、第 $5$ 个格子上，从而到达目标状态。

在第四个表演计划中，当 Alice 和 Bob 分别位于第 $3$、第 $4$ 个格子时，无法执行任何动作。

• 若 Alice 向右走，两人都会站在第 $4$ 个格子上，违反条件。
• 若 Bob 向左走，两人都会站在第 $3$ 个格子上，违反条件。
• 若 Bob 使用第 $4$ 个格子上的跳板落到第 $2$ 个格子，他将站在位于第 $3$ 个格子的 Alice 左侧，违反条件。

因此，无法到达 Alice 和 Bob 分别站在第 $1$、第 $2$ 个格子的目标状态。

限制条件

• 给出的所有数均为整数。
• $2 \le N \le 200\,000$
• $0 \le M \le 200\,000$
• $1 \le Q \le 500\,000$
• 对于每个整数 $i$（$1 \le i \le M$），$1 \le x_i,y_i \le N$ 且 $x_i \ne y_i$。
• 对于每个整数 $j$（$1 \le j \le Q$），$1 \le a_j<b_j \le N$ 且 $1 \le c_j<d_j \le N$。

子任务

1. （$8$ 分）$N,M,Q \le 100$。
2. （$14$ 分）对于每个整数 $i$（$1 \le i \le M$），$x_i<y_i$。
3. （$13$ 分）$N \le 3\,000$。
4. （$13$ 分）$Q \le 10$。
5. （$52$ 分）没有额外限制。

翻译由 ChatGPT-5.6 完成