Học viện JOI có \(N\) học sinh, được đánh số từ \(1\) đến \(N\).

Học viện sắp tổ chức một buổi trao đổi quà. Mỗi học sinh đã chuẩn bị một món quà để mang đến; món quà của học sinh \(i\) (\(1 \le i \le N\)) có giá trị \(A_i\). Các học sinh không muốn nhận một món quà có giá trị quá thấp so với quà của mình. Cụ thể, học sinh \(i\) sẽ không hài lòng nếu nhận món quà có giá trị nhỏ hơn \(B_i\). Luôn có \(B_i<A_i\).

Tuy nhiên, không nhất thiết cả \(N\) học sinh đều tham gia. Chủ tịch K, người đứng đầu học viện, đang xem xét \(Q\) nhóm học sinh có thể tham gia. Nhóm thứ \(j\) (\(1 \le j \le Q\)) gồm \(R_j-L_j+1\) học sinh \(L_j,L_j+1,\ldots,R_j\).

Một nhóm có ít nhất hai học sinh được gọi là có thể trao đổi quà nếu có cách trao đổi quà trong nhóm sao cho không ai nhận lại quà của chính mình và không ai cảm thấy không hài lòng. Chính xác hơn, nhóm gồm \(m\) học sinh \(p_1,p_2,\ldots,p_m\) (\(m \ge 2\)) có thể trao đổi quà khi và chỉ khi tồn tại một hoán vị \(q_1,q_2,\ldots,q_m\) của \(p_1,p_2,\ldots,p_m\) thỏa mãn cả hai điều kiện sau:

• \(p_k \ne q_k\) với mọi \(1 \le k \le m\).
• \(A_{q_k} \ge B_{p_k}\) với mọi \(1 \le k \le m\).

Ở đây, \(q_k\) là số hiệu của học sinh tặng quà cho học sinh \(p_k\).

Chủ tịch K muốn buổi trao đổi quà thành công. Cho thông tin về các học sinh và các nhóm, hãy xác định với từng nhóm liệu nhóm đó có thể trao đổi quà hay không.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn theo dạng:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N
Q
L_1 R_1
L_2 R_2
...
L_Q R_Q

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa Yes nếu nhóm thứ \(j\) có thể trao đổi quà, hoặc No nếu không thể.

Ràng buộc

• \(2 \le N \le 500\,000\).
• \(1 \le B_i<A_i \le 2N\) (\(1 \le i \le N\)).
• Các giá trị \(A_1,B_1,A_2,B_2,\ldots,A_N,B_N\) đôi một khác nhau.
• \(1 \le Q \le 200\,000\).
• \(1 \le L_j<R_j \le N\) (\(1 \le j \le Q\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. 4 điểm: \(N \le 10\), \(Q \le 10\).
2. 5 điểm: \(N \le 18\), \(Q \le 10\).
3. 10 điểm: \(N \le 100\,000\), \(A_1 \ge 2N-2\), \(B_1=1\), \(Q=1\), \(L_1=1\), \(R_1=N\).
4. 31 điểm: \(N \le 100\,000\), \(Q \le 10\).
5. 8 điểm: \(N \le 100\,000\); \(A_i<A_{i+1}\) và \(B_i<B_{i+1}\) với mọi \(1 \le i \le N-1\).
6. 12 điểm: \(N \le 100\,000\); \(A_i<A_{i+1}\) với mọi \(1 \le i \le N-1\).
7. 18 điểm: \(N \le 100\,000\).
8. 12 điểm: Không có ràng buộc bổ sung.

Ví dụ

4
3 8 5 7
2 6 1 4
3
3 4
1 3
1 4

Yes
No
Yes

3
5 6 3
1 4 2
1
1 3

Yes

5
3 4 6 9 10
1 2 5 7 8
3
1 5
1 2
2 4

No
Yes
No

10
2 5 8 10 12 14 16 17 19 20
1 4 7 6 11 13 9 3 18 15
8
2 9
1 6
2 8
2 4
1 2
1 6
7 10
5 8

No
No
Yes
No
No
No
Yes
Yes

Nguồn

Gift Exchange, JOI 2024, vòng chung kết quốc gia, bài 4 (tiếng Anh) · Đề tiếng Nhật. Tác giả: Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.