Problem Description

Alice and Bob, two acrobats, are preparing to perform on a balance beam. The balance beam consists of $N$ consecutive cells, numbered from $1$ to $N$ from left to right.

During the performance, at any moment, each acrobat must stand on exactly one cell. To ensure safety, at all times the index of the cell where Alice stands must be less than the index of the cell where Bob stands. That is, Alice must always stand to the left of Bob, and they cannot stand on the same cell.

There are $M$ springboards installed on the balance beam. The $i$-th ($1 \le i \le M$) springboard is installed on cell $x_i$. After an acrobat standing on cell $x_i$ uses this springboard, they will land exactly on cell $y_i$.

Multiple springboards may be installed on the same cell. Both acrobats may use any springboard any number of times.

A performance consists of executing any number of actions (possibly $0$). In one action, exactly one of the two acrobats performs one of the following two operations:

1. Walk: Alice may move one cell to the right from her current cell; Bob may move one cell to the left from his current cell. Alice cannot walk left, and Bob cannot walk right.
2. Jump: Choose and use a springboard installed on the cell where the acrobat is currently standing. That is, for some integer $i$ ($1 \le i \le M$), an acrobat standing on cell $x_i$ may use the $i$-th springboard and land on cell $y_i$.

After an action is performed, Alice must still stand on a cell to the left of Bob. Any action that would violate this condition cannot be performed.

The two acrobats have $Q$ performance plans. The $j$-th ($1 \le j \le Q$) performance plan is given by four integers $a_j,b_j,c_j,d_j$ satisfying $1 \le a_j<b_j \le N$ and $1 \le c_j<d_j \le N$. The $j$-th plan is called valid if, by performing some sequence of actions, starting from the state where Alice and Bob stand on cells $a_j$ and $b_j$ respectively, they can eventually end in the state where they stand on cells $c_j$ and $d_j$ respectively.

For each of the $Q$ performance plans, determine whether it is valid.

Input Format

The first line contains two space-separated integers $N$ and $M$.

The next $M$ lines give information about the $M$ springboards. Line $i$ ($1 \le i \le M$) contains two space-separated integers $x_i$ and $y_i$, describing the $i$-th springboard.

The next line contains an integer $Q$, the number of performance plans.

The next $Q$ lines describe the $Q$ performance plans. Line $j$ ($1 \le j \le Q$) contains four space-separated integers $a_j,b_j,c_j,d_j$, describing the $j$-th performance plan.

Output Format

Output $Q$ lines starting from the first line. Line $j$ ($1 \le j \le Q$) should be the answer to the $j$-th performance plan: if it is possible to start with Alice and Bob standing on cells $a_j$ and $b_j$ respectively and eventually make them stand on cells $c_j$ and $d_j$ respectively, output YES; otherwise output 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

Hint

Explanation of Sample 1

In the second performance plan, Alice and Bob start on cells $2$ and $3$ respectively. Bob uses the springboard on cell $3$ to move to cell $5$. Then Alice and Bob are on cells $2$ and $5$ respectively, reaching the target state.

In the fourth performance plan, when Alice and Bob are on cells $3$ and $4$ respectively, no action can be performed.

• If Alice walks right, both would stand on cell $4$, violating the condition.
• If Bob walks left, both would stand on cell $3$, violating the condition.
• If Bob uses the springboard on cell $4$ and lands on cell $2$, he would stand to the left of Alice on cell $3$, violating the condition.

Therefore, it is impossible to reach the target state where Alice and Bob stand on cells $1$ and $2$ respectively.

Constraints

• All given values are integers.
• $2 \le N \le 200\,000$.
• $0 \le M \le 200\,000$.
• $1 \le Q \le 500\,000$.
• For each integer $i$ ($1 \le i \le M$), $1 \le x_i,y_i \le N$ and $x_i \ne y_i$.
• For each integer $j$ ($1 \le j \le Q$), $1 \le a_j<b_j \le N$ and $1 \le c_j<d_j \le N$.

Subtasks

1. ($8$ points) $N,M,Q \le 100$.
2. ($14$ points) For each integer $i$ ($1 \le i \le M$), $x_i<y_i$.
3. ($13$ points) $N \le 3\,000$.
4. ($13$ points) $Q \le 10$.
5. ($52$ points) No additional constraints.

Translated by ChatGPT-5.6.

Translated by ChatGPT 5