Căn phòng của JOI-kun có dạng hình chữ nhật, được chia thành một lưới gồm \(N \times M\) ô. Có \(N\) hàng nằm theo hướng đông - tây và \(M\) cột nằm theo hướng nam - bắc. Ô ở hàng thứ \(i\) tính từ phía bắc và cột thứ \(j\) tính từ phía tây được ký hiệu là \((i,j)\), với \(1 \le i \le N\), \(1 \le j \le M\). Một số ô có đặt đồ nội thất. Nếu \(C_{i,j}=1\) thì ô \((i,j)\) có đồ nội thất; nếu \(C_{i,j}=0\) thì ô đó không có đồ nội thất.
Một cách bố trí đồ nội thất được gọi là hợp lý nếu có thể đi từ ô \((1,1)\) đến ô \((N,M)\) mà không đi qua ô có đồ nội thất, bằng cách liên tiếp di chuyển sang ô kề phía nam hoặc phía đông. Cách bố trí ban đầu được bảo đảm là hợp lý.
JOI-kun sẽ thực hiện lần lượt \(Q\) thao tác. Ở thao tác thứ \(k\) (\(1 \le k \le Q\)), nếu việc đặt thêm một món đồ nội thất vào ô \((X_k,Y_k)\) vẫn giữ cho cách bố trí hợp lý, cậu sẽ đặt món đồ đó vào ô này. Ngược lại, cậu không làm gì.
JOI-kun không thực hiện thao tác tại ô đã có đồ nội thất từ đầu hoặc ô đã được chọn trong một thao tác trước đó. Hai ô \((1,1)\) và \((N,M)\) không có đồ nội thất, và cậu cũng không thực hiện thao tác tại hai ô này.
Cho kích thước căn phòng, cách bố trí ban đầu và các ô được chọn trong các thao tác, hãy xác định với mỗi thao tác liệu JOI-kun có đặt thêm đồ nội thất hay không.
Dữ liệu vào
Đọc dữ liệu từ đầu vào chuẩn. Tất cả các giá trị trong dữ liệu vào đều là số nguyên.
- Dòng đầu chứa hai số \(N,M\).
- Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(M\) số \(C_{i,1},C_{i,2},\ldots,C_{i,M}\).
- Dòng tiếp theo chứa số \(Q\).
- Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa hai số \(X_k,Y_k\).
Dữ liệu ra
Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa 1 nếu JOI-kun đặt thêm đồ nội thất vào ô \((X_k,Y_k)\) trong thao tác thứ \(k\), hoặc 0 nếu không.
Ràng buộc
- \(1 \le N \le 1000\).
- \(1 \le M \le 1000\).
- \(0 \le C_{i,j} \le 1\) với \(1 \le i \le N\), \(1 \le j \le M\).
- \(C_{1,1}=0\) và \(C_{N,M}=0\).
- Cách bố trí ban đầu là hợp lý.
- \(1 \le Q \le N \times M\).
- \(1 \le X_k \le N\) và \(1 \le Y_k \le M\) với \(1 \le k \le Q\).
- \((X_k,Y_k) \ne (1,1)\) và \((X_k,Y_k) \ne (N,M)\) với \(1 \le k \le Q\).
- \(C_{X_k,Y_k} \ne 1\) với \(1 \le k \le Q\).
- \((X_k,Y_k) \ne (X_l,Y_l)\) với \(1 \le k < l \le Q\).
Phân nhóm
Mọi phân nhóm đều thỏa mãn toàn bộ ràng buộc ở trên.
- 5 điểm: \(N \le 100\) và \(M \le 100\).
- 95 điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
2 3
0 0 1
0 0 0
3
2 2
2 1
1 2
Output
0
1
0
Giải thích
Thao tác đầu tiên được thực hiện tại ô \((2,2)\). Nếu đặt thêm đồ nội thất vào ô này thì cách bố trí không còn hợp lý. Vì vậy, JOI-kun không đặt đồ nội thất vào ô \((2,2)\) và kết quả là 0.
Thao tác thứ hai được thực hiện tại ô \((2,1)\). Nếu đặt thêm đồ nội thất vào ô này, ta vẫn có thể đi qua các ô \((1,1),(1,2),(2,2),(2,3)\) theo thứ tự đó, nên cách bố trí vẫn hợp lý. Vì vậy, JOI-kun đặt đồ nội thất vào ô \((2,1)\) và kết quả là 1.
Thao tác thứ ba được thực hiện tại ô \((1,2)\). Vì ô \((2,1)\) đã có đồ nội thất, việc đặt thêm đồ nội thất vào ô \((1,2)\) sẽ khiến cách bố trí không còn hợp lý. Vì vậy, kết quả là 0.
Ví dụ 2
Input
2 5
0 0 0 0 0
0 0 0 1 0
2
1 2
2 2
Output
0
1
Giải thích
Thao tác đầu tiên được thực hiện tại ô \((1,2)\). Nếu đặt thêm đồ nội thất vào ô này thì cách bố trí không còn hợp lý. Vì vậy, JOI-kun không đặt thêm đồ nội thất và kết quả là 0. Lưu ý rằng đường đi qua các ô \((1,1),(2,1),(2,2),(2,3),(1,3),(1,4),(1,5),(2,5)\) theo thứ tự đó không đi qua đồ nội thất. Tuy nhiên, bước từ \((2,3)\) đến \((1,3)\) đi về phía bắc, nên không thỏa mãn điều kiện của một cách bố trí hợp lý.
Thao tác thứ hai được thực hiện tại ô \((2,2)\). Nếu đặt thêm đồ nội thất vào ô này, cách bố trí vẫn hợp lý vì có thể đi qua các ô \((1,1),(1,2),(1,3),(1,4),(1,5),(2,5)\) theo thứ tự đó. Vì vậy, JOI-kun đặt thêm đồ nội thất vào ô \((2,2)\) và kết quả là 1.
Nguồn
JOI Open Contest 2020, bài 1. Bản dịch từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản (JCIOI), theo giấy phép CC BY-SA 4.0.
