Trên một dãy \(N\) ô, hai nghệ sĩ Alice và Bob luôn đứng ở hai ô khác nhau, với Alice ở bên trái Bob. Có \(M\) bệ nhảy; bệ \(i\) đưa người từ ô \(x_i\) đến ô \(y_i\).

Mỗi hành động chỉ di chuyển một người: Alice có thể đi sang phải một ô, Bob có thể đi sang trái một ô, hoặc một người dùng bệ nhảy tại ô của mình. Sau mỗi hành động, Alice vẫn phải ở bên trái Bob.

Một ô có thể có nhiều bệ nhảy. Cả Alice và Bob đều có thể dùng bất kỳ bệ nào không giới hạn số lần; bệ \(i\) chỉ dùng được khi người đó đang ở ô \(x_i\) và đưa người đó đến đúng ô \(y_i\). Một kế hoạch có thể dùng \(0\) hoặc nhiều hành động.

Với mỗi kế hoạch \((a,b,c,d)\), hãy xác định có thể bắt đầu với Alice ở \(a\), Bob ở \(b\) và kết thúc ở \(c,d\) hay không.

Dữ liệu vào

• Dòng đầu chứa \(N,M\).
• \(M\) dòng tiếp theo chứa \(x_i,y_i\).
• Dòng tiếp theo chứa \(Q\).
• \(Q\) dòng tiếp theo chứa \(a,b,c,d\).

Dữ liệu ra

In \(Q\) dòng; dòng thứ \(j\) là YES nếu kế hoạch thứ \(j\) khả thi, ngược lại là NO.

Ràng buộc

• \(2\le N\le200000\), \(0\le M\le200000\), \(1\le Q\le500000\).
• \(1\le x_i,y_i\le N\), \(x_i\ne y_i\).
• \(1\le a<b\le N\), \(1\le c<d\le N\).

Phân nhóm

• Nhóm 1 (8 điểm): \(N,M,Q\le100\).
• Nhóm 2 (14 điểm): \(x_i<y_i\) với mọi bệ nhảy.
• Nhóm 3 (13 điểm): \(N\le3000\).
• Nhóm 4 (13 điểm): \(Q\le10\).
• Nhóm 5 (52 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

KOI 2026 Round 2, problem Acrobatics. Tài liệu, dữ liệu chấm và mã nguồn mẫu từ Korean Olympiad in Informatics, phát hành theo CC BY-NC-SA 4.0.