31627번 - Road Service 2 서브태스크다국어

In JOI city, there is a grid-shaped road network consisting of $H$ infinitely long east-west roads and $W$ infinitely long north-south roads. Intersection $(i, j)$ ($1 ≤ i ≤ H$, $1 ≤ j ≤ W$) is the intersection where the $i$-th northernmost east-west road and the $j$-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 $i$-th northernmost east-west road ($1 ≤ i ≤ H$) connecting intersection $(i, j)$ and intersection $(i, j + 1)$ ($1 ≤ j ≤ W - 1$) is closed if $A_{i, j} = 0$ and passable if $A_{i, j} = 1$.
• The segment in the $j$-th westernmost north-south road ($1 ≤ j ≤ W$) connecting intersection $(i, j)$ and intersection $(i + 1, j)$ ($1 ≤ i ≤ H - 1$) is closed if $B_{i, j} = 0$ and passable if $B_{i, j} = 1$.
• The other part of the roads (the part of roads outside the $H \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 $i$ satisfying $1 ≤ i ≤ H$ and doing the following:

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

The repair takes $C_i$ days. Note that $C_i$ is either $1$ or $2$.

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 $Q$ questions. The $k$-th questions ($1 ≤ k ≤ Q$) is as follows:

Is there a repair plan that makes $T_k$ intersections $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \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.

$H$ $W$ $Q$

$A_{1,1}A_{1,2} \cdots A_{1,W-1}$

$A_{2,1}A_{2,2} \cdots A_{2,W-1}$

$\vdots$

$A_{H,1}A_{H,2} \cdots A_{H,W-1}$

$B_{1,1}B_{1,2} \cdots B_{1,W}$

$B_{2,1}B_{2,2} \cdots B_{2,W}$

$\vdots$

$B_{H-1,1}B_{H-1,2} \cdots B_{H-1,W}$

$C_1$ $C_2$ $\cdots$ $C_H$

$Query_1$

$Query_2$

$\vdots$

$Query_Q$

Here, $Query_k$ ($1 ≤ k ≤ Q$) is as follows:

$T_k$

$X_{k,1}$ $Y_{k,1}$

$X_{k,2}$ $Y_{k,2}$

$\vdots$

$X_{k,T_k}$ $Y_{k,T_k}$

Write $Q$ lines to the standard output. In the $k$-th line ($1 ≤ k ≤ Q$), output the minimum possible period, in days, of a repair plan that makes $T_k$ intersections $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \dots , (X_{k,T_k}, Y_{k,T_k})$ mutually reachable if such a repair plan exists. Otherwise, output -1.

• $2 ≤ H$.
• $2 ≤ W$.
• $H \times W ≤ 1\, 000\, 000$.
• $1 ≤ Q ≤ 100\, 000$.
• $A_{i, j}$ is either $0$ or $1$ ($1 ≤ i ≤ H$, $1 ≤ j ≤ W - 1$).
• $B_{i, j}$ is either $0$ or $1$ ($1 ≤ i ≤ H - 1$, $1 ≤ j ≤ W$).
• $C_i$ is either $1$ or $2$ ($1 ≤ i ≤ H$).
• $2 ≤ T_k$ ($1 ≤ k ≤ Q$).
• $T1 + T2 + \cdots + T_Q ≤ 200\, 000$.
• $1 ≤ X_{k,l} ≤ H$ ($1 ≤ k ≤ Q$, $1 ≤ l ≤ T_k$).
• $1 ≤ Y_{k,l} ≤ W$ ($1 ≤ k ≤ Q$, $1 ≤ l ≤ T_k$).
• $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \dots , (X_{k,T_k}, Y_{k,T_k})$ are distinct ($1 ≤ k ≤ Q$).
• Given values are all integers.