곡예

$N$개의 칸이 일렬로 나열된 평균대 위에서 두 곡예사 Alice와 Bob이 공연을 진행하려고 한다. 평균대의 칸에는 왼쪽부터 오른쪽으로 $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가 $a_j$번 칸, Bob이 $b_j$번 칸에 서 있는 상태로 공연을 시작하여, Alice가 $c_j$번 칸, Bob이 $d_j$번 칸에 서 있는 상태로 공연을 마치는 것이 가능하다면, $j$번째 공연 계획은 유효하다.

$Q$개의 공연 계획에 대해서 각 계획이 유효한지 판정하라.

• 주어지는 모든 수는 정수이다.
• $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점) 추가 제약 조건 없음.

첫 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 차례대로 주어진다.

그다음 $M$개의 줄에 걸쳐, $M$개의 점프대에 대한 정보가 주어진다. 이 중 $i$ $(1 \le i \le M)$번째 줄에는 $i$번째 점프대를 나타내는 두 정수 $x_i$와 $y_i$가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 공연 계획의 개수를 나타내는 정수 $Q$가 주어진다.

그다음 $Q$개의 줄에 걸쳐, $Q$개의 공연 계획에 대한 정보가 주어진다. 이 중 $j$ $(1 \le j \le Q)$번째 줄에는 $j$번째 공연 계획을 나타내는 네 정수 $a_j$, $b_j$, $c_j$, $d_j$가 공백으로 구분되어 차례대로 주어진다.

첫 줄부터 $Q$개의 줄에 걸쳐, 답을 출력한다. 이 중 $j$ $(1 \le j \le Q)$번째 줄에는 $j$번째 공연 계획에 대한 답을 출력한다. 만약 Alice가 $a_j$번 칸, Bob이 $b_j$번 칸에 서 있는 상태로 공연을 시작하여, Alice가 $c_j$번 칸, Bob이 $d_j$번 칸에 서 있는 상태로 공연을 마칠 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.