题目描述

译自 JOI Open 2020 T1「家具の配置 / Furniture」

JOI 君的房间是一个 $N \times M$ 的矩形网格。房间有 $N$ 行（平行于东西方向）和 $M$ 列（平行于南北方向）。
从北数第 $i$ 行、从西数第 $j$ 列的格子记作 $(i,j)$。

每个格子中可能放有家具。对于 $1 \le i \le N, 1 \le j \le M$，若 $C_{i,j} = 1$，则 $(i,j)$ 格有家具；若 $C_{i,j} = 0$，则没有家具。

如果从 $(1,1)$ 出发，只能向南或向东走，并且不经过有家具的格子，能到达 $(N,M)$，则称这种家具摆放方式是好的。
题目保证初始时家具摆放方式是好的。

JOI 君会进行 $Q$ 次操作，第 $k$ 次操作（$1 \le k \le Q$）如下：

• 尝试在 $(X_k, Y_k)$ 格放置一个新家具。
• 如果放置后家具摆放方式仍然是好的，则放置；否则不放置。

注意：

• 不会在初始已有家具或之前已放置过家具的格子中放置新家具。
• 初始 $(1,1)$ 与 $(N,M)$ 没有家具。
• 不会对这两个格子进行操作。

给定房间大小、初始家具摆放情况和操作序列，请判断每次操作是否会进行。

---

输入格式

第一行：$N, M$
接下来 $N$ 行：每行 $M$ 个整数 $C_{i,j}$，表示初始家具摆放情况。
接下来一行：$Q$
接下来 $Q$ 行：每行 $X_k, Y_k$，表示操作位置。

---

输出格式

输出 $Q$ 行。第 $k$ 行输出对第 $k$ 次操作的回答：

• 如果 JOI 君可以在 $(X_k,Y_k)$ 放置新家具，输出 $1$；
• 否则输出 $0$。

---

样例 1

输入

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

输出

0
1
0

解释

• 第一次操作 $(2,2)$：如果放置，则无法从 $(1,1)$ 只向南或向东走到 $(2,3)$，因此不放，输出 $0$。
• 第二次操作 $(2,1)$：放置后仍存在路径 $(1,1) \to (1,2) \to (2,2) \to (2,3)$，因此放置，输出 $1$。
• 第三次操作 $(1,2)$：放置后会阻断唯一路径，因此不放，输出 $0$。

---

样例 2

输入

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

输出

0
1

解释

• 第一次操作 $(1,2)$：如果放置，则无法只向南或向东走到 $(2,5)$（不能向北走），因此不放，输出 $0$。
• 第二次操作 $(2,2)$：放置后路径 $(1,1) \to (1,2) \to (1,3) \to (1,4) \to (1,5) \to (2,5)$ 可行，因此放置，输出 $1$。

---

数据范围与提示

• $1 \le N, M \le 1000$
• $0 \le C_{i,j} \le 1$
• $1 \le Q \le N \times M$
• 保证：
  • $C_{1,1} = C_{N,M} = 0$
  • 初始家具摆放方式是好的
  • $1 \le X_k \le N, 1 \le Y_k \le M$
  • $(X_k,Y_k) \ne (1,1)$ 且 $(X_k,Y_k) \ne (N,M)$
  • $C_{X_k,Y_k} \ne 1$（初始时该格无家具）
  • $(X_k,Y_k)$ 互不相同

子任务：

• 子任务 1（5 分）：$N, M \le 100$
• 子任务 2（95 分）：无附加限制