在 JOI 市，有一个网格状的道路网络，由 $H$ 条无限长的东西向道路和 $W$ 条无限长的南北向道路组成。交叉路口 $(i, j)$ ($1 \le i \le H, 1 \le j \le W$) 是第 $i$ 条最北端的道路与第 $j$ 条最西端的道路的交点。

目前，部分道路因路况不佳而关闭。具体而言，道路状态如下：

• 第 $i$ 条最北端的道路 ($1 \le i \le H$) 上，连接交叉路口 $(i, j)$ 和 $(i, j+1)$ ($1 \le j \le W-1$) 的路段，若 $A_{i, j} = 0$ 则关闭，若 $A_{i, j} = 1$ 则通行。
• 第 $j$ 条最西端的道路 ($1 \le j \le W$) 上，连接交叉路口 $(i, j)$ 和 $(i+1, j)$ ($1 \le i \le H-1$) 的路段，若 $B_{i, j} = 0$ 则关闭，若 $B_{i, j} = 1$ 则通行。
• 道路的其他部分（$H \times W$ 个交叉路口之外的部分）均关闭。

JOI 市市长 K 先生决定制定一份道路网络维修计划。维修计划由零次或多次维修组成。每次维修通过选择一个满足 $1 \le i \le H$ 的整数 $i$ 并执行以下操作来完成：

对于每个满足 $1 \le j \le W-1$ 的整数 $j$，使第 $i$ 条最北端的道路上连接交叉路口 $(i, j)$ 和 $(i, j+1)$ 的路段变为可通行（如果该路段原本是关闭的）。

维修需要 $C_i$ 天。注意 $C_i$ 为 $1$ 或 $2$。

由于维修计划中的两次维修不能并行进行，因此维修计划的周期等于该计划中各次维修所耗时间之和。

K 先生认为确保城市设施之间的路线非常重要，并向你提出了 $Q$ 个问题。第 $k$ 个问题 ($1 \le k \le Q$) 如下：

是否存在一种维修计划，使得 $T_k$ 个交叉路口 $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \dots, (X_{k,T_k}, Y_{k,T_k})$ 相互可达？如果存在，这种维修计划的最小可能周期是多少？

请编写一个程序，在给定道路网络状态、维修每条东西向道路所需天数以及 K 先生的问题详情后，回答所有问题。

输入格式

从标准输入读取以下数据：

$H \ W \ Q$ $A_{1,1} A_{1,2} \dots A_{1,W-1}$ $A_{2,1} A_{2,2} \dots A_{2,W-1}$ $\vdots$ $A_{H,1} A_{H,2} \dots A_{H,W-1}$ $B_{1,1} B_{1,2} \dots B_{1,W}$ $B_{2,1} B_{2,2} \dots B_{2,W}$ $\vdots$ $B_{H-1,1} B_{H-1,2} \dots B_{H-1,W}$ $C_1 \ C_2 \dots C_H$ $\text{Query}_1$ $\text{Query}_2$ $\vdots$ $\text{Query}_Q$

其中 $\text{Query}_k$ ($1 \le k \le Q$) 的格式如下：

$T_k$ $X_{k,1} \ Y_{k,1}$ $X_{k,2} \ Y_{k,2}$ $\vdots$ $X_{k,T_k} \ Y_{k,T_k}$

输出格式

向标准输出写入 $Q$ 行。在第 $k$ 行 ($1 \le k \le Q$) 中，如果存在使 $T_k$ 个交叉路口 $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \dots, (X_{k,T_k}, Y_{k,T_k})$ 相互可达的维修计划，则输出该计划的最小可能周期（以天为单位）；否则输出 $-1$。

数据范围

• $2 \le H$
• $2 \le W$
• $H \times W \le 1\,000\,000$
• $1 \le Q \le 100\,000$
• $A_{i, j}$ 为 $0$ 或 $1$ ($1 \le i \le H, 1 \le j \le W-1$)
• $B_{i, j}$ 为 $0$ 或 $1$ ($1 \le i \le H-1, 1 \le j \le W$)
• $C_i$ 为 $1$ 或 $2$ ($1 \le i \le H$)
• $2 \le T_k$ ($1 \le k \le Q$)
• $T_1 + T_2 + \dots + T_Q \le 200\,000$
• $1 \le X_{k,l} \le H$ ($1 \le k \le Q, 1 \le l \le T_k$)
• $1 \le Y_{k,l} \le W$ ($1 \le k \le Q, 1 \le l \le T_k$)
• $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \dots, (X_{k,T_k}, Y_{k,T_k})$ 互不相同 ($1 \le k \le Q$)
• 给定值均为整数

子任务

1. (10 分) $C_i = 1$ ($1 \le i \le H$), $Q \le 5$, $T_k = 2$ ($1 \le k \le Q$), $A_{i, j} = 0$ ($1 \le i \le H, 1 \le j \le W-1$)
2. (6 分) $C_i = 1$ ($1 \le i \le H$), $Q \le 5$, $T_k = 2$ ($1 \le k \le Q$)
3. (15 分) $C_i = 1$ ($1 \le i \le H$), $Q \le 5$
4. (11 分) $C_i = 1$ ($1 \le i \le H$), $T_k = 2$ ($1 \le k \le Q$)
5. (6 分) $C_i = 1$ ($1 \le i \le H$)
6. (12 分) $Q \le 5$
7. (26 分) $T_k = 2$ ($1 \le k \le Q$)
8. (14 分) 无附加限制

样例

样例输入 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

1
3
0
-1

说明

下图展示了道路网络的当前状态。灰色部分为关闭，蓝色部分为可通行。

• 在第一个问题中，进行 $i = 2$ 的维修将使道路网络状态改变，交叉路口 $(1, 1)$ 和 $(3, 3)$ 将相互连通。该维修计划的周期为 1 天，且不存在周期更短的维修计划使 $(1, 1)$ 和 $(3, 3)$ 相互可达，因此第一行输出 1。
• 在第二个问题中，分别进行 $i = 1, 2, 3$ 的维修将使交叉路口 $(3, 1)$ 和 $(1, 2)$ 相互可达。该维修计划的周期为 3 天，且不存在周期更短的维修计划使 $(3, 1)$ 和 $(1, 2)$ 相互可达，因此第二行输出 3。
• 在第三个问题中，交叉路口 $(2, 3)$ 和 $(3, 3)$ 已经相互可达，因此第三行输出 0。
• 在第四个问题中，不存在使交叉路口 $(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

样例输出 2

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

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

样例输出 4

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

样例输出 5

4
1

该样例输入满足子任务 6, 8 的限制。