Road Service 2

문제

In JOI city, there is a grid-shaped road network consisting of $HH$ infinitely long east-west roads and $WW$ infinitely long north-south roads. Intersection $(i,j)(i,\; j)$ (1 ≤ i ≤ H, 1 ≤ j ≤ W) is the intersection where the $ii$-th northernmost east-west road and the $jj$-th westernmost north-south road cross.

Currently, part of the roads is closed due to poor road conditions. Specifically, the status of the roads is as follows:

• The segment in the $ii$-th northernmost east-west road (1 ≤ i ≤ H) connecting intersection $(i,j)(i,\; j)$ and intersection $(i,j+1)(i,\; j\; +\; 1)$ (1 ≤ j ≤ W - 1) is closed if $A_{i,j}=0A\_\{i,\; j\}\; =\; 0$ and passable if $A_{i,j}=1A\_\{i,\; j\}\; =\; 1$.
• The segment in the $jj$-th westernmost north-south road (1 ≤ j ≤ W) connecting intersection $(i,j)(i,\; j)$ and intersection $(i+1,j)(i\; +\; 1,\; j)$ (1 ≤ i ≤ H - 1) is closed if $B_{i,j}=0B\_\{i,\; j\}\; =\; 0$ and passable if $B_{i,j}=1B\_\{i,\; j\}\; =\; 1$.
• The other part of the roads (the part of roads outside the $H\times WH\; \backslash times\; W$ intersections) is closed.

President K, the mayor of JOI city, decided to make a repair plan of the road network. A repair plan consists of zero or more repairs. A repair is done by choosing an integer $ii$ satisfying 1 ≤ i ≤ H and doing the following:

For every integer $jj$ satisfying 1 ≤ j ≤ W - 1, make the segment in the $ii$-th northernmost east-west road connecting intersection $(i,j)(i,\; j)$ and intersection $(i,j+1)(i,\; j\; +\; 1)$ passable (if it is closed).

The repair takes $C_{i}C\_i$ days. Note that $C_{i}C\_i$ is either $11$ or $22$.

Since no two repairs in a repair plan can be done in parallel, the period of a repair plan is equal to the sum of the time taken by repairs consisting the repair plan.

President K thinks that securing the route between city facilities is important and asks you $QQ$ questions. The $kk$-th questions (1 ≤ k ≤ Q) is as follows:

Is there a repair plan that makes $T_{k}T\_k$ intersections $(X_{k,1},Y_{k,1}),(X_{k,2},Y_{k,2}),\dots ,(X_{k,T_k},Y_{k,T_k})(X\_\{k,1\},\; Y\_\{k,1\}),\; (X\_\{k,2\},\; Y\_\{k,2\}),\; \backslash dots\; ,\; (X\_\{k,T\_k\},\; Y\_\{k,T\_k\})$ mutually reachable? If so, what is the minimum possible period of such a repair plan?

Write a program which, given the status of the road network, the days taken by repairing each east-west road and the details of the questions by President K, answers all the questions.

입력

Read the following data from the standard input.

$HH$ $WW$ $QQ$

$A_{1,1}{A}_{1,2}\cdots A_{1,W-1}A\_\{1,1\}A\_\{1,2\}\; \backslash cdots\; A\_\{1,W-1\}$

$A_{2,1}{A}_{2,2}\cdots A_{2,W-1}A\_\{2,1\}A\_\{2,2\}\; \backslash cdots\; A\_\{2,W-1\}$

$\mathrm{⋮}\backslash vdots$

$A_{H,1}{A}_{H,2}\cdots A_{H,W-1}A\_\{H,1\}A\_\{H,2\}\; \backslash cdots\; A\_\{H,W-1\}$

$B_{1,1}{B}_{1,2}\cdots B_{1,W}B\_\{1,1\}B\_\{1,2\}\; \backslash cdots\; B\_\{1,W\}$

$B_{2,1}{B}_{2,2}\cdots B_{2,W}B\_\{2,1\}B\_\{2,2\}\; \backslash cdots\; B\_\{2,W\}$

$\mathrm{⋮}\backslash vdots$

$B_{H-1,1}{B}_{H-1,2}\cdots B_{H-1,W}B\_\{H-1,1\}B\_\{H-1,2\}\; \backslash cdots\; B\_\{H-1,W\}$

$C_{1}C\_1$ $C_{2}C\_2$ $\cdots \backslash cdots$ $C_{H}C\_H$

$Quer{y}_{1}Query\_1$

$Quer{y}_{2}Query\_2$

$\mathrm{⋮}\backslash vdots$

$Quer{y}_{Q}Query\_Q$

Here, $Quer{y}_{k}Query\_k$ (1 ≤ k ≤ Q) is as follows:

$T_{k}T\_k$

$X_{k,1}X\_\{k,1\}$ $Y_{k,1}Y\_\{k,1\}$

$X_{k,2}X\_\{k,2\}$ $Y_{k,2}Y\_\{k,2\}$

$\mathrm{⋮}\backslash vdots$

$X_{k,T_k}X\_\{k,T\_k\}$ $Y_{k,T_k}Y\_\{k,T\_k\}$

출력

Write $QQ$ lines to the standard output. In the $kk$-th line (1 ≤ k ≤ Q), output the minimum possible period, in days, of a repair plan that makes $T_{k}T\_k$ intersections $(X_{k,1},Y_{k,1}),(X_{k,2},Y_{k,2}),\dots ,(X_{k,T_k},Y_{k,T_k})(X\_\{k,1\},\; Y\_\{k,1\}),\; (X\_\{k,2\},\; Y\_\{k,2\}),\; \backslash dots\; ,\; (X\_\{k,T\_k\},\; Y\_\{k,T\_k\})$ mutually reachable if such a repair plan exists. 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