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.

1. 5 điểm: \(N \le 100\) và \(M \le 100\).
2. 95 điểm: Không có ràng buộc bổ sung.

Ví dụ

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

0
1
0

2 5
0 0 0 0 0
0 0 0 1 0
2
1 2
2 2

0
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.