JOI City Road Repair Plan

JOI City has a grid‐shaped road network consisting of \(H\) east–west roads (numbered from north to south) and \(W\) north–south roads (numbered from west to east). The intersection of the \(i\)th east–west road and the \(j\)th north–south road is denoted by \((i,j)\) for \(1 \le i \le H\) and \(1 \le j \le W\).

Some of the roads are blocked due to disrepair. The details are as follows:

• For each \(1 \le i \le H\) and \(1 \le j \le W-1\), if \(A_{i,j} = 0\) then the segment between \((i,j)\) and \((i,j+1)\) on the \(i\)th east–west road is blocked; if \(A_{i,j} = 1\) it is open.
• For each \(1 \le j \le W\) and \(1 \le i \le H-1\), if \(B_{i,j} = 0\) then the segment between \((i,j)\) and \((i+1,j)\) on the \(j\)th north–south road is blocked; if \(B_{i,j} = 1\) it is open.
• All parts of the roads outside the \(H \times W\) intersections are blocked.

The mayor has planned a series of repairs. A repair plan consists of zero or more repairs. In one repair, you choose an integer \(i\) (\(1 \le i \le H\)) and repair every horizontal segment on the \(i\)th east–west road. In other words, for every \(1 \le j \le W-1\), if the segment between \((i,j)\) and \((i,j+1)\) is blocked, it becomes open. This repair takes \(C_i\) days (where \(C_i\) is either 1 or 2). Repairs are performed sequentially, so the total time is the sum of the days required for each repair.

There are \(Q\) queries. In the \(k\)th query you are given \(T_k\) intersections \((X_{k,1},Y_{k,1}), (X_{k,2},Y_{k,2}), \dots, (X_{k,T_k},Y_{k,T_k})\). For each query, determine if there exists a repair plan such that these intersections become mutually reachable using only open roads. If yes, output the minimum total number of days required; otherwise, output \(-1\).

Note: The only roads that can be repaired are the horizontal ones. Vertical roads remain in their original condition.

inputFormat

The input is given in the following format:

H W
A1,1 A1,2 ... A1,W-1
A2,1 A2,2 ... A2,W-1
... 
AH,1 AH,2 ... AH,W-1
B1,1 B1,2 ... B1,W
B2,1 B2,2 ... B2,W
... 
BH-1,1 BH-1,2 ... BH-1,W
C1 C2 ... CH
Q
T1 X1,1 Y1,1 X1,2 Y1,2 ... X1,T1 Y1,T1
T2 X2,1 Y2,1 ...
...
TQ XQ,1 YQ,1 ... XQ,TQ YQ,TQ

Here, \(A_{i,j}\) (\(1 \le i \le H,\; 1 \le j \le W-1\)) describes the status of the horizontal road segments initially, \(B_{i,j}\) (\(1 \le j \le W,\; 1 \le i \le H-1\)) describes the vertical road segments, and \(C_i\) (each either 1 or 2) is the number of days needed to repair the entire \(i\)th east–west road.

outputFormat

For each query, output the minimum total number of days required to make the given intersections mutually reachable using only open roads, or \(-1\) if it is not possible.

sample

2 3
1 0
0 1
1 0 1
1 2
2
2 1 1 1 3
2 1 2 2 2

1
-1