Problem Description

JOI City has a grid-like road network consisting of $H$ infinitely long east–west roads and $W$ north–south roads. The intersection of the $i\ (1 \leq i \leq H)$-th east–west road counted from the north and the $j\ (1 \leq j \leq W)$-th north–south road counted from the west is called intersection $(i, j)$.

Now, due to long-term disrepair, some road segments are blocked. The blocking status is as follows:

• If $A_{i, j}=0\ (1 \leq i \leq H, 1 \leq j \leq W-1)$, then on the $i$-th east–west road counted from the north, the segment between intersections $(i, j)$ and $(i, j+1)$ is blocked. If $A_{i, j}=1$, then it is passable.
• If $B_{i, j}=0\ (1 \leq j \leq W, 1 \leq i \leq H-1)$, then on the $j$-th north–south road counted from the west, the segment between intersections $(i, j)$ and $(i+1, j)$ is blocked. If $B_{i, j}=1$, then it is passable.
• All other parts of the roads, namely the parts outside the $H \times W$ intersections, are blocked.

The city mayor, Director K, decided to make a road repair plan. A repair plan consists of at least $0$ repairs. In one repair, choose an integer $i\ (1 \leq i \leq H)$, and perform the following operation:

For all integers $j$ satisfying $1 \leq j \leq W-1$, if on the $i$-th east–west road counted from the north the segment between intersections $(i, j)$ and $(i, j+1)$ is blocked, make it passable. This process takes $C_i$ days in total, where $C_i$ is $1$ or $2$.

Multiple repairs in the repair plan cannot be carried out at the same time. Therefore, the number of days required to execute the repair plan is the sum of the days required by all repairs included in the plan.

To allow important facilities in the city to be mutually reachable, Director K asks you $Q$ questions. The $k$-th question $(1 \leq k \leq Q)$ is as follows:

Is there a repair plan that makes the $T_k$ intersections $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots ,(X_{k, T_{k}}, Y_{k, T_{k}})$ mutually reachable using only passable roads. If such a plan exists, what is the minimum number of days needed to execute such a repair plan.

Given the blocking status of the road network, the days required to repair each road, and the contents of Director K's questions, write a program to answer all of Director K's questions.

Input Format

The first line contains three integers $H,W,Q$.

The next $H$ lines each contain a string of length $W-1$, representing $A_{i,1},A_{i,2},\ldots ,A_{i,W-1}$.

The next $H-1$ lines each contain a string of length $W$, representing $B_{i,1},B_{i,2},\ldots ,B_{i,W}$.

The next line contains $H$ space-separated integers $C_1,C_2,\ldots ,C_H$.

Then there are $Q$ queries, each given in the following form:

The first line contains an integer $T_k$.
The next $T_k$ lines each contain two integers $X_{k,i},Y_{k,i}$.

Output Format

Output $Q$ lines. In the $k$-th line $(1 \leq k \leq Q)$, if there exists a repair plan that makes the $T_k$ intersections $(X_{k, 1}, Y_{k, 1}),(X_{k, 2}, Y_{k, 2}), \ldots ,(X_{k, T_{k}}, Y_{k, T_{k}})$ mutually reachable, output the minimum number of days needed to execute such a repair plan. Otherwise, output $-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

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

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

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

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

Hint

For all input data, it holds that:

• $2 \leq H$.
• $2 \leq W$.
• $H \times W \leq 10^6$.
• $1 \leq Q \leq 10^5$.
• $A_{i, j}$ is $0$ or $1\ (1 \leq i \leq H, 1 \leq j \leq W-1)$.
• $B_{i, j}$ is $0$ or $1\ (1 \leq i \leq H-1,1 \leq j \leq W)$.
• $C_{i}$ is $1$ or $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}})$ are all distinct $(1 \leq k \leq Q)$.

The detailed additional constraints and scores for subtasks are shown in the table below.

Translated by ChatGPT 5