题目描述

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

JOI 君房间的形状是矩形，由 $N\times M$ 个单元格组成。这个房间有 $N$ 个横排，每个横排平行于东西方向。有 $M$ 个竖排，每个竖排平行于南北方向。从北数第 $i$ 个，从西数第 $j$ 个格子表示为 $(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 君会进行 $Q$ 次操作，第 $k\ (1\le k\le Q)$ 次操作按如下方法进行：

• 如果一件新家具放置在 $(X_k,Y_k)$ 格中后，家具摆放方式仍然是好的，那么就在 $(X_k,Y_k)$ 格中放一件新家具，否则他不进行操作。

注意，他不会将新家具放在初始有家具或进行过家具摆放操作的格子中。初始 $(1,1)$ 与 $(N,M)$ 格子中不会有家具，并且他不会对这两个格子进行操作。给定房间大小，初始家具摆放情况和他要进行操作的格子，写一个程序确定每次操作会不会进行。

输入格式

第一行两个整数 $N,M$；

接下来 $N$ 行，每行 $M$ 个整数 $C_{i,j}$，表示初始家具摆放情况。

接下来一行一个整数 $Q$，表示询问次数；

接下来 $Q$ 行，每行两个整数 $X_k,Y_k$，表示每次新家具的摆放位置。

输出格式

输出 $Q$ 行到标准输出。第 $k\ (1\le k\le Q)$ 行输出对第 $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)$。如果 $(2,2)$ 放一件新家具的话，家具摆放方式就不是好的了。因此，JOI 君不会将新家具放在 $(2,2)$。输出 $0$。

第二个操作将新家具放在 $(2,1)$。如果 $(2,1)$ 放一件新家具的话，按 $(1,1),(1,2),(2,2),(2,3)$ 的顺序就可以从 $(1,1)$ 走到 $(2,3)$，家具摆放方式仍然是好的。因此，JOI 君会将新家具放在 $(2,1)$。输出 $1$。

第三个操作将新家具放在 $(1,2)$。因为 $(2,1)$ 已经放有家具，如果 $(2,2)$ 放一件新家具的话，家具摆放方式就不是好的了。因此，JOI 君不会将新家具放在 $(1,2)$。输出 $0$。

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

0
1

第一个操作将新家具放在 $(1,2)$。如果 $(1,2)$ 放一件新家具的话，家具摆放方式就不是好的了。因此，JOI 君不会将新家具放在 $(1,2)$。输出 $0$。注意如果我们按 $(1,1),(2,1),(2,2),(2,3),(1,3),(1,4),(1,5),(2,5)$ 的顺序仍然可以从 $(1,1)$ 走到 $(2,5)$，但是由于从 $(2,3)$ 走到 $(1,3)$ 是向北走，因此不满足好的家具摆放方式的条件。

第二个操作将新家具放在 $(2,2)$。如果 $(2,2)$ 放一件新家具的话，按 $(1,1),(1,2),(1,3),(1,4),(1,5),(2,5)$ 的顺序就可以从 $(1,1)$ 走到 $(2,5)$，家具摆放方式仍然是好的。因此，JOI 君会将新家具放在 $(2,2)$。输出 $1$。

数据范围与提示

对于全部数据，$1\le N,M\le 10^3,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\ (1\le k\le Q)$；
• $(X_k,Y_k)\neq (1,1)$ 且 $(X_k,Y_k)\neq (N,M)\ (1\le k\le Q)$；
• $C_{X_k,Y_k}\neq 1\ (1\le k\le Q)$；
• $(X_k,Y_k)\neq (X_l,Y_l)\ (1\le k<l\le Q)$。

详细子任务附加限制及分值如下：

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