题目描述

题目译自 JOI 2024 Final T5 「道路網の整備 2 / Road Service 2」

JOI 市有一个由 $H$ 条东西向的无限长道路和 $W$ 条南北向的道路组成的网格状道路网。从北边数第 $i$（$1 \leq i \leq H$）条的东西向的道路和从西边数第 $j$（$1 \leq j \leq W$）条的南北向的道路相交的地方称作交叉点 $(i, j)$。

现在，由于道路年久失修，一部分道路被封锁了。具体的封锁情况如下：

1. 如果 $A_{i,j}=0$（$1 \leq i \leq H, 1 \leq j \leq W-1$），则从北边数第 $i$ 条的东西向的道路的，交叉点 $(i, j)$ 和交叉点 $(i, j+1)$ 之间的部分就是封锁的；如果 $A_{i,j}=1$ 则是可以通行的。
2. 如果 $B_{i,j}=0$（$1 \leq j \leq W, 1 \leq i \leq H-1$），从西边数第 $j$ 条的南北向的道路的，交叉点 $(i, j)$ 和交叉点 $(i+1, j)$ 之间的部分就是封锁的；如果 $B_{i,j}=1$ 就是可以通行的。
3. 道路的其他部分，即 $H \times W$ 个交叉点外面的部分都是封锁的。

JOI 市的市长 K 理事长决定制定一个道路维修计划。维修计划由大于等于 $0$ 次维修构成。一次维修时选择一个满足的整数 $i$（$1 \leq i \leq H$），然后进行以下的操作：

• 对于所有满足 $1 \leq j \leq W-1$ 的整数 $j$，如果从北边数第 $i$ 条的东西向的道路的，交叉点 $(i, j)$ 和交叉点 $(i, j+1)$ 之间的部分是封锁的话，将其变成可以通行的。
• 这个过程总共需要 $C_i$ 天。其中，$C_i$ 为 $1$ 或 $2$。

维修计划里包含的多次维修不能同时进行。因此，维修计划的执行所需要的天数是维修计划里包含的所有维修所需要的天数的总和。

为了让市里的重要设施之间能够互相通行，K 理事长向你提出了 $Q$ 个问题。第 $k$（$1 \leq k \leq Q$）个问题是这样的：

• 是否存在一个维修计划，能够让 $T_k$ 个交叉点 $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \ldots, (X_{k,T_k}, Y_{k,T_k})$ 之间，只通过可以通行的道路互相通行。
• 如果存在的话，执行这样的维修计划最少需要多少天。

给定道路网的封锁情况，各条道路的维修所需要的天数，K 理事长的问题的内容，编写一个程序来回答 K 理事长的所有问题。

输入格式

第一行包含三个整数 $H, W, Q$。

接下来 $H$ 行，每行包含一个长度为 $W-1$ 的字符串，表示 $A_{i,1}, A_{i,2}, \ldots, A_{i,W-1}$。

接下来 $H-1$ 行，每行包含一个长度为 $W$ 的字符串，表示 $B_{i,1}, B_{i,2}, \ldots, B_{i,W}$。

接下来一行包含 $H$ 个用空格分隔的整数 $C_1, C_2, \ldots, C_H$。

接下来有 $Q$ 个询问，每个询问用以下形式给出：

• 第一行包含一个整数 $T_k$。
• 接下来 $T_k$ 行每行包含两个整数 $X_{k,i}, Y_{k,i}$。

输出格式

输出 $Q$ 行。第 $k$ 行（$1 \leq k \leq Q$）里，如果存在一个维修计划，能够让 $T_k$ 个交叉点 $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \ldots, (X_{k,T_k}, Y_{k,T_k})$ 之间互相通行，就输出执行这样的维修计划最少需要多少天。否则输出 $-1$。

样例 1

输入

$4$ $3$ $4$ $00$ $00$ $00$ $00$ $100$ $001$ $000$ $1$ $1$ $1$ $1$ $2$ $1$ $1$ $3$ $3$ $2$ $3$ $1$ $1$ $2$ $2$ $2$ $3$ $3$ $3$ $2$ $4$ $2$ $3$ $2$

输出

$1$ $3$ $0$ $-1$

说明

下面的图是现在的封锁情况。灰色表示封锁，蓝色表示可以通行。

第 $1$ 个问题中，如果选择 $i=2$ 的维修，封锁情况会变成下图的样子，交叉点 $(1,1),(3,3)$ 之间就能够互相通行了。这个只有 $1$ 次维修的维修计划的执行所需要的天数是 $1$，没有比这个更少的天数能够让交叉点 $(1,1),(3,3)$ 之间互相通行的维修计划，所以输出 $1$。

第 $2$ 个问题中，如果选择 $i=1,2,3$ 的 $3$ 次维修，交叉点 $(3,1),(1,2)$ 之间就能够互相通行了。这个 $3$ 次维修的维修计划的执行所需要的天数是 $3$，没有比这个更少的天数能够让交叉点 $(3,1),(1,2)$ 之间互相通行的维修计划，所以输出 $3$。

第 $3$ 个问题中，不需要进行任何维修，就可以让交叉点 $(2,3),(3,3)$ 之间互相通行，所以输出 $0$。

第 $4$ 个问题中，不存在一个维修计划，能够让交叉点 $(4,2),(3,2)$ 之间互相通行，所以输出 $-1$。

这个样例满足子任务 $1,2,3,4,5,6,7,8$ 的限制。

样例 2

输入

$4$ $4$ $4$ $100$ $110$ $011$ $010$ $0010$ $1001$ $0101$ $1$ $1$ $1$ $1$ $2$ $1$ $2$ $3$ $1$ $2$ $1$ $4$ $4$ $1$ $2$ $3$ $2$ $1$ $2$ $2$ $4$ $3$ $1$ $1$

输出

$1$ $3$ $2$ $2$

说明

这个样例满足子任务 $2,3,4,5,6,7,8$ 的限制。

样例 3

输入

$7$ $3$ $3$ $10$ $00$ $00$ $10$ $00$ $01$ $00$ $110$ $101$ $011$ $001$ $110$ $100$ $1$ $1$ $1$ $1$ $1$ $1$ $1$ $3$ $7$ $2$ $3$ $1$ $3$ $2$ $3$ $3$ $1$ $6$ $3$ $2$ $3$ $7$ $2$ $2$ $1$ $3$ $7$ $3$ $5$ $2$ $1$ $2$ $7$ $2$ $3$ $1$

输出

$3$ $2$ $4$

说明

这个样例满足子任务 $3,5,6,8$ 的限制。

样例 4

输入

$4$ $3$ $3$ $00$ $00$ $10$ $00$ $110$ $011$ $001$ $1$ $2$ $2$ $2$ $2$ $1$ $1$ $3$ $1$ $2$ $4$ $3$ $2$ $1$ $2$ $4$ $1$ $1$ $3$

输出

$1$ $2$ $5$

说明

这个样例满足子任务 $6,7,8$ 的限制。

样例 5

输入

$7$ $3$ $2$ $01$ $00$ $00$ $00$ $00$ $10$ $01$ $100$ $110$ $011$ $001$ $101$ $001$ $1$ $1$ $2$ $1$ $1$ $2$ $2$ $3$ $7$ $2$ $1$ $3$ $5$ $1$ $5$ $1$ $1$ $2$ $2$ $3$ $1$ $2$ $3$ $4$ $2$

输出

$4$ $1$

说明

这个样例满足子任务 $6,8$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq H$
• $2 \leq W$
• $H \times W \leq 10^6$
• $1 \leq Q \leq 10^5$
• $A_{i,j}$ 为 $0$ 或 $1$（$1 \leq i \leq H, 1 \leq j \leq W-1$）
• $B_{i,j}$ 为 $0$ 或 $1$（$1 \leq i \leq H-1, 1 \leq j \leq W$）
• $C_i$ 为 $1$ 或 $2$（$1 \leq i \leq H$）
• $2 \leq T_k$（$1 \leq k \leq Q$）
• $T_1 + T_2 + \cdots + T_Q \leq 2 \times 10^5$
• $1 \leq X_{k,l} \leq H$（$1 \leq k \leq Q, 1 \leq l \leq T_k$）
• $1 \leq Y_{k,l} \leq W$（$1 \leq k \leq Q, 1 \leq l \leq T_k$）
• $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \ldots, (X_{k,T_k}, Y_{k,T_k})$ 各不相同（$1 \leq k \leq Q$）

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

子任务	附加限制	分值
$1$	$C_i=1$（$1 \leq i \leq H$），$Q \leq 5$，$T_k=2$（$1 \leq k \leq Q$），$A_{i,j}=0$（$1 \leq i \leq H, 1 \leq j \leq W-1$）	$10$
$2$	$C_i=1$（$1 \leq i \leq H$），$Q \leq 5$，$T_k=2$（$1 \leq k \leq Q$）	$6$
$3$	$C_i=1$（$1 \leq i \leq H$），$Q \leq 5$	$15$
$4$	$C_i=1$（$1 \leq i \leq H$），$T_k=2$（$1 \leq k \leq Q$）	$11$
$5$	$C_i=1$（$1 \leq i \leq H$）	$6$
$6$	$Q \leq 5$	$12$
$7$	$T_k=2$（$1 \leq k \leq Q$）	$26$
$8$	无附加限制	$14$