JOI-kun 的房间是矩形的，是一个 $N \times M$ 的网格。房间共有 $N$ 行，每行平行于东西方向；共有 $M$ 列，每列平行于南北方向。从北往南数第 $i$ 行、从西往东数第 $j$ 列的方格（$1 \le i \le N, 1 \le j \le 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$，则方格 $(i, j)$ 中没有家具。
如果我们可以通过重复向南或向东移动，从方格 $(1, 1)$ 走到方格 $(N, M)$ 且不经过任何有家具的方格，则称该家具摆放方式是“美观的”。保证初始的家具摆放方式是美观的。
JOI-kun 将执行 $Q$ 次操作。第 $k$ 次操作（$1 \le k \le Q$）按如下方式进行： 如果将一块新家具放置在方格 $(X_k, Y_k)$ 后，家具摆放方式依然是美观的，那么他就在方格 $(X_k, Y_k)$ 放置一块新家具。否则，他什么也不做。
注意，他不会对初始时已有家具的方格或已经执行过操作的方格进行操作。方格 $(1, 1)$ 和方格 $(N, M)$ 中没有家具，且他不会对这些方格进行操作。请编写一个程序，给定房间大小、初始家具摆放情况以及他将要进行操作的方格，确定每次操作是否成功放置了家具。
输入格式
从标准输入读取以下数据。所有输入值均为整数。
$N \ M$ $C_{1,1} \ C_{1,2} \ \dots \ C_{1,M}$ $C_{2,1} \ C_{2,2} \ \dots \ C_{2,M}$ $\vdots$ $C_{N,1} \ C_{N,2} \ \dots \ C_{N,M}$ $Q$ $X_1 \ Y_1$ $X_2 \ Y_2$ $\vdots$ $X_Q \ Y_Q$
输出格式
向标准输出写入 $Q$ 行。第 $k$ 行（$1 \le k \le Q$）应包含 1（如果 JOI-kun 在第 $k$ 次操作中在方格 $(X_k, Y_k)$ 放置了新家具）或 0（否则）。
数据范围
- $1 \le N \le 1\,000$
- $1 \le M \le 1\,000$
- $0 \le C_{i, j} \le 1$（$1 \le i \le N, 1 \le j \le M$）
- $C_{1,1} = 0$
- $C_{N,M} = 0$
- 初始家具摆放方式是美观的
- $1 \le Q \le N \times M$
- $1 \le X_k \le N$（$1 \le k \le Q$）
- $1 \le Y_k \le M$（$1 \le k \le Q$）
- $(X_k, Y_k) \neq (1, 1)$（$1 \le k \le Q$）
- $(X_k, Y_k) \neq (N, M)$（$1 \le k \le Q$）
- $C_{X_k, Y_k} = 0$（$1 \le k \le Q$）
- $(X_k, Y_k) \neq (X_l, Y_l)$（$1 \le k < l \le Q$）
子任务
- (5 分) $N \le 100, M \le 100$
- (95 分) 无附加限制
样例
输入 1
2 3 0 0 1 0 0 0 3 2 2 2 1 1 2
输出 1
0 1 0
说明 1
第一次操作针对方格 $(2, 2)$。如果将新家具放置在 $(2, 2)$，则摆放方式将不再美观。因此，JOI-kun 实际上没有在 $(2, 2)$ 放置家具。输出应为 0。
第二次操作针对方格 $(2, 1)$。如果将新家具放置在 $(2, 1)$，例如，我们可以按 $(1, 1), (1, 2), (2, 2), (2, 3)$ 的顺序移动，摆放方式依然美观。因此，JOI-kun 在 $(2, 1)$ 放置了新家具。输出应为 1。
第三次操作针对方格 $(1, 2)$。由于方格 $(2, 1)$ 已经放置了家具，如果再在 $(1, 2)$ 放置家具，摆放方式将不再美观。因此，输出应为 0。
输入 2
2 5 0 0 0 0 0 0 0 0 1 0 2 1 2 2 2
输出 2
0 1
说明 2
第一次操作针对方格 $(1, 2)$。如果将新家具放置在 $(1, 2)$，则摆放方式将不再美观。因此，JOI-kun 实际上没有放置家具，输出应为 0。注意，如果我们按 $(1, 1), (2, 1), (2, 2), (2, 3), (1, 3), (1, 4), (1, 5), (2, 5)$ 的顺序移动，我们不会经过有家具的方格。然而，由于从 $(2, 3)$ 到 $(1, 3)$ 的移动方向是向北的，这不满足美观摆放的条件。
第二次操作针对方格 $(2, 2)$。如果将新家具放置在 $(2, 2)$，摆放方式依然美观，因为我们可以按 $(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 5)$ 的顺序移动。因此，JOI-kun 在 $(2, 2)$ 放置了新家具，输出应为 1。