题目描述

一个房间的布置可以被表示为一个 $n$ 行 $m$ 列的 01 矩阵，其中为 1 的位置表示放置了一件家具，0 表示没有放置。

如果你可以从房间的左上角 $(1,1)$ 只向右和向下走到达右下角 $(n,m)$，且路径上不经过有家具的格子，那么我们定义这样的房间布置是好的。

给定房间的初始布置 $C$，对于位置 $(i,j)\ (1\le i \le n, 1\le j \le m)$，$C_{i,j}=1$ 表示有家具，$C_{i,j}=0$ 则没有。保证初始布置一定是好的。

现在要进行 $Q$ 次操作，第 $k$ 次操作形如 $(X_k,Y_k)$，表示尝试在 $(X_k,Y_k)$ 处放置一个家具。如果在 $(X_k,Y_k)$ 处放置后整个布置仍然是好的，那么就放置这个家具；否则不进行任何操作。对于每次操作，输出这个家具是否被成功放置。

保证尝试放置家具的位置 $(X_k,Y_k)$ 在初始布置和之前的任何一次操作中均没有被放置过家具。保证 $(1,1)$ 和 $(n,m)$ 处没有家具。

输入格式

第一行两个整数 $n,m$，表示房间的长宽。

接下来是一个 $n\times m$ 的 01 矩阵 $C$，表示房间的初始布置。保证初始布置是好的。

接下来是一个整数 $Q$ 表示操作次数。

然后是 $Q$ 行操作，每行给定 $X_k,Y_k$ 两个整数表示尝试放置的位置。

输出格式

一共 $Q$ 行，第 $k$ 行输出 1 或 0 表示第 $k$ 次操作是否成功放置。如果成功输出 1，否则输出 0。

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

提示

样例解释 1

第一次操作尝试在 $(2,2)$ 处放置，但放置后 $(1,1)$ 无法到达 $(n,m)$，因此输出 0，不进行任何修改。

第二次操作尝试在 $(2,1)$ 处放置，放置后存在这样一条合法路径：$(1,1)\to(1,2)\to(2,2)\to(2,3)$。因此该布置仍然是好的，所以 $(2,1)$ 位置被放置一个家具，输出 1。

第三次操作尝试在 $(1,2)$ 处放置，因为上一次已经在 $(2,1)$ 放置了一个家具，此时 $(1,1)$ 无法到达 $(n,m)$，因此输出 0，不进行任何修改。

样例解释 2

第一次操作尝试在 $(1,2)$ 处放置，此时这个布置不是好的。注意这条路径 $(1,1)\to (2,1)\to (2,2)\to (2,3)\to(1,3)\to(1,4)\to(1,5)\to(2,5)$ 不是一条合法路径，因为不满足只向右向下走的条件。因此输出 0，不进行任何修改。

第一次操作尝试在 $(2,2)$ 处放置，此时存在一条合法路径 $(1,1)\to (1,2)\to(1,3)\to(1,4)\to(1,5)\to(2,5)$。因此该布置仍然是好的，所以 $(2,2)$ 位置被放置一个家具，输出 1。

数据规模与约定

本题采用捆绑测试。

• Subtask 1 （5 pts）：$n\le 100,m\le 100$；
• Subtask 2 （95 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $n\le 1000,m\le 1000$；
• $C_{i,j}\in \{0,1\}\ (1\le i\le n,1\le j\le m)$；
• $C_{1,1}=C_{n,m}=0$；
• 初始布置是好的；
• $1\le Q\le n\times m$；
• $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), 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)$。

说明

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