D. Tìm kiếm trên ma trận (Mã bài: MATRIXSEARCH)

Cho ma trận dòng, cột. Các dòng đánh số từ đến , các cột đánh số từ đến . Ma trận có điểm đặc biệt:

• Các phần tử trên một dòng là tăng dần
• Các phần tử trên một cột là tăng dần

Có truy vấn dạng như sau:

• : Cho biết trong ma trận có phần tử hay không?
• : tăng tất cả các phần tử của ma trận con có đỉnh trái trên là thêm đơn vị

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương
• dòng tiếp theo, mỗi dòng chứa số nguyên dương
• Dòng tiếp theo chứa số nguyên dương
• dòng tiếp theo, mỗi dòng chứa một truy vấn dạng:

Kết quả:

• Ghi ra nhiều dòng, mỗi dòng theo thứ tự là câu trả lời cho truy vấn loại . Ghi Y nếu có phần tử , ngược lại ghi N.

Ví dụ:

Dữ liệu:

3 4
11 13 14 17
13 15 19 21
18 20 23 42
9
1 42
1 27
2 2 2 4
1 27
2 1 3 7
1 20
1 32
1 19
1 42

Kết quả:

Y
N
Y
N
Y
Y
N