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$-th east-west road from the north $(1 \leq i \leq H)$ and the $j$-th north-south road from the west $(1 \leq j \leq W)$ is called intersection $(i, j)$.

Currently, some roads are blocked due to aging. The blocking details are as follows:
- If $A_{i, j}=0\ (1 \leq i \leq H, 1 \leq j \leq W-1)$, the section between intersection $(i, j)$ and intersection $(i, j+1)$ on the $i$-th east-west road is blocked; if $A_{i, j}=1$, it is passable.
- If $B_{i, j}=0\ (1 \leq j \leq W, 1 \leq i \leq H-1)$, the section between intersection $(i, j)$ and intersection $(i+1, j)$ on the $j$-th north-south road is blocked; if $B_{i, j}=1$, it is passable.
- All other parts outside the $H \times W$ intersections are blocked.

The mayor of JOI City, Chairman K, has decided to formulate a road maintenance plan. The plan consists of at least $0$ repairs. Each repair involves selecting an integer $i\ (1 \leq i \leq H)$ and performing the following operation:

For all integers $j\ (1 \leq j \leq W-1)$, if the section between intersection $(i, j)$ and intersection $(i, j+1)$ on the $i$-th east-west road is blocked, it becomes passable. This process takes $C_{i}$ days, where $C_{i}$ is either $1$ or $2$.

Repairs included in the plan cannot be performed simultaneously. Therefore, the total number of days required to execute the plan is the sum of the days required for all repairs.

To ensure that important facilities in the city can communicate with each other, Chairman K has asked you $Q$ questions. The $k$-th question $(1 \leq k \leq Q)$ is as follows:

Is there a maintenance plan that allows 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}})$ to be mutually accessible only through passable roads? If such a plan exists, what is the minimum number of days required to execute it?

Given the blocking status of the road network, the maintenance days required for each road, and the content of Chairman K's questions, write a program to answer all of Chairman K's questions.

Input Format

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

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

The next $H-1$ lines, each containing a string of length $W$, represent $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$.

The next $Q$ queries are given in the following format:

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

Output Format

Output $Q$ lines. The $k$-th line $(1 \leq k \leq Q)$ should contain the minimum number of days required to execute a maintenance plan that allows 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}})$ to be mutually accessible, or $-1$ if no such plan exists.

Sample Input and Output

Input Sample #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

Output Sample #1

1
3
0
-1

Input Sample #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

Output Sample #2

1
3
2
2

Input Sample #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

Output Sample #3

3
2
4

Input Sample #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

Output Sample #4

1
2
5

Input Sample #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

Output Sample #5

4
1

Notes/Hints

For all input data, the following conditions are satisfied:

• $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 distinct $(1 \leq k \leq Q)$

Detailed subtask additional restrictions and scores are as follows:

见题面 Input 部分

见题面 Output 部分