Một con lạc đà không bướu (llama) muốn đi xuyên qua Cao nguyên Andes. Nó có một bản đồ của cao nguyên dưới dạng một lưới gồm \(N \times M\) ô vuông. Các hàng của bản đồ được đánh số từ \(0\) đến \(N-1\) từ trên xuống dưới, và các cột được đánh số từ \(0\) đến \(M-1\) từ trái sang phải. Ô của bản đồ ở hàng \(i\) và cột \(j\) (với \(0 \le i < N, 0 \le j < M\)) được ký hiệu là \((i, j)\).

Lạc đà đã nghiên cứu khí hậu của cao nguyên và phát hiện ra rằng tất cả các ô trong cùng một hàng của bản đồ có cùng nhiệt độ, và tất cả các ô trong cùng một cột của bản đồ có cùng độ ẩm. Lạc đà đưa cho bạn hai mảng số nguyên \(T\) và \(H\) có độ dài lần lượt là \(N\) và \(M\). Ở đây, \(T[i]\) (với \(0 \le i < N\)) chỉ nhiệt độ của các ô ở hàng \(i\), và \(H[j]\) (với \(0 \le j < M\)) chỉ độ ẩm của các ô ở cột \(j\).

Lạc đà cũng đã nghiên cứu thảm thực vật của cao nguyên và nhận thấy rằng một ô \((i, j)\) là không có thực vật khi và chỉ khi nhiệt độ của nó lớn hơn độ ẩm của nó, tức là \(T[i] > H[j]\).

Lạc đà chỉ có thể di chuyển qua cao nguyên bằng cách đi theo các đường đi hợp lệ. Một đường đi hợp lệ là một dãy các ô phân biệt thoả mãn các điều kiện sau:

• Mỗi cặp ô liên tiếp trên đường đi có chung một cạnh.
• Tất cả các ô trên đường đi đều không có thực vật.

Nhiệm vụ của bạn là trả lời \(Q\) câu hỏi. Với mỗi câu hỏi, bạn được cho bốn số nguyên: \(L, R, S\) và \(D\). Bạn phải xác định xem có tồn tại một đường đi hợp lệ thoả mãn các điều kiện sau hay không:

• Đường đi bắt đầu tại ô \((0, S)\) và kết thúc tại ô \((0, D)\).
• Tất cả các ô trên đường đi đều nằm trong các cột từ \(L\) đến \(R\), bao gồm cả hai đầu mút.

Đảm bảo rằng cả hai ô \((0, S)\) và \((0, D)\) đều không có thực vật.

Bạn cần cài đặt hai hàm trong tệp obstacles.h để tương tác với bộ chấm.

Hàm đầu tiên cần cài đặt là:

void initialize(std::vector<int> T, std::vector<int> H)

• \(T\): một mảng có độ dài \(N\) chỉ nhiệt độ của mỗi hàng.
• \(H\): một mảng có độ dài \(M\) chỉ độ ẩm của mỗi cột.
• Hàm này được gọi đúng một lần cho mỗi test, trước bất kỳ lệnh gọi nào tới can_reach.

Hàm thứ hai cần cài đặt là:

bool can_reach(int L, int R, int S, int D)

• \(L, R, S, D\): các số nguyên mô tả một câu hỏi.
• Hàm này được gọi \(Q\) lần cho mỗi test.

Hàm này phải trả về true khi và chỉ khi tồn tại một đường đi hợp lệ từ ô \((0, S)\) đến ô \((0, D)\), sao cho tất cả các ô trên đường đi đều nằm trong các cột từ \(L\) đến \(R\), bao gồm cả hai đầu mút.

Chi tiết cài đặt

Bạn không được cài đặt hàm main trong tệp giải. Cần cài đặt hai hàm initialize và can_reach như mô tả ở trên trong tệp obstacles.h.

Ràng buộc

• \(1 \le N, M, Q \le 200\,000\)
• \(0 \le T[i] \le 10^9\) với mỗi \(i\) thoả mãn \(0 \le i < N\).
• \(0 \le H[j] \le 10^9\) với mỗi \(j\) thoả mãn \(0 \le j < M\).
• \(0 \le L \le R < M\)
• \(L \le S \le R\)
• \(L \le D \le R\)
• Cả hai ô \((0, S)\) và \((0, D)\) đều không có thực vật.

Phân nhóm

• Subtask 1 (10 điểm): \(L = 0, R = M - 1\) với mỗi câu hỏi. \(N = 1\).
• Subtask 2 (14 điểm): \(L = 0, R = M - 1\) với mỗi câu hỏi. \(T[i-1] \le T[i]\) với mỗi \(i\) thoả mãn \(1 \le i < N\).
• Subtask 3 (13 điểm): \(L = 0, R = M - 1\) với mỗi câu hỏi. \(N = 3\) và \(T = [2, 1, 3]\).
• Subtask 4 (21 điểm): \(L = 0, R = M - 1\) với mỗi câu hỏi. \(Q \le 10\).
• Subtask 5 (25 điểm): \(L = 0, R = M - 1\) với mỗi câu hỏi.
• Subtask 6 (17 điểm): Không có ràng buộc bổ sung.

Ví dụ

Xét lệnh gọi sau:

initialize([2, 1, 3], [0, 1, 2, 0])

Lệnh gọi này tương ứng với bản đồ trong đó các ô không có thực vật (màu trắng) và các ô có thực vật (màu xanh) như sau: với \(N = 3\) hàng và \(M = 4\) cột, các ô \((0, 2), (1, 1), (1, 2)\) là có thực vật, các ô còn lại đều không có thực vật.

Ở câu hỏi đầu tiên, xét lệnh gọi:

can_reach(0, 3, 1, 3)

Trong tình huống này, các cột được giới hạn trong khoảng từ \(L = 0\) đến \(R = 3\). Lạc đà có thể đi từ ô \((0, 1)\) đến ô \((0, 3)\) thông qua đường đi hợp lệ sau:

Do đó, lệnh gọi này phải trả về true.

Ở câu hỏi thứ hai, xét lệnh gọi:

can_reach(1, 3, 1, 3)

Trong tình huống này, không tồn tại đường đi hợp lệ từ ô \((0, 1)\) đến ô \((0, 3)\) sao cho tất cả các ô trên đường đi đều nằm trong các cột từ \(1\) đến \(3\), bao gồm cả hai đầu mút. Do đó, lệnh gọi này phải trả về false.

3 4
2 1 3
0 1 2 0
2
0 3 1 3
1 3 1 3

1
0

Chấm điểm

Định dạng đầu vào của bộ chấm mẫu:

N M
T[0] T[1] ... T[N-1]
H[0] H[1] ... H[M-1]
Q
L[0] R[0] S[0] D[0]
L[1] R[1] S[1] D[1]
...
L[Q-1] R[Q-1] S[Q-1] D[Q-1]

Ở đây, \(L[k], R[k], S[k]\) và \(D[k]\) (với \(0 \le k < Q\)) chỉ các tham số cho mỗi lệnh gọi tới can_reach.

Định dạng đầu ra của bộ chấm mẫu:

A[0]
A[1]
...
A[Q-1]

Ở đây, \(A[k]\) (với \(0 \le k < Q\)) bằng \(1\) nếu lệnh gọi can_reach(L[k], R[k], S[k], D[k]) trả về true, và bằng \(0\) trong trường hợp ngược lại.