2024-ho-t5_Road_Service_2 (JOI JOI)
Time limit: 3 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: implementation, data structures, sparse table, dynamic programming

# 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<sub>i,j</sub>* = 0 and passable if *A<sub>i,j</sub>* = 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<sub>i,j</sub>* = 0 and passable if *B<sub>i,j</sub>* = 1.
*   The other part of the roads (the part of roads outside the *H* × *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<sub>i</sub>* days. Note that *C<sub>i</sub>* 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 of the repair plan.

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

Is there a repair plan that makes *T<sub>k</sub>* intersections (*X<sub>k,1</sub>*, *Y<sub>k,1</sub>*), (*X<sub>k,2</sub>*, *Y<sub>k,2</sub>*), ..., (*X<sub>k,Tk</sub>*, *Y<sub>k,Tk</sub>*) 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.

#### Input

Read the following data from the standard input.

```
H W Q
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
Query1
Query2
...
QueryQ
```

Here, Query<sub>k</sub> (1 ≤ *k* ≤ *Q*) is as follows:

```
Tk
Xk,1 Yk,1
Xk,2 Yk,2
...
Xk,Tk Yk,Tk
```

#### Output

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<sub>k</sub>* intersections (*X<sub>k,1</sub>*, *Y<sub>k,1</sub>*), (*X<sub>k,2</sub>*, *Y<sub>k,2</sub>*), ..., (*X<sub>k,Tk</sub>*, *Y<sub>k,Tk</sub>*) mutually reachable if such a repair plan exists. Otherwise, output -1.

#### Constraints

*   2 ≤ *H*.
*   2 ≤ *W*.
*   *H* × *W* ≤ 1 000 000.
*   1 ≤ *Q* ≤ 100 000.
*   *A<sub>i,j</sub>* is either 0 or 1 (1 ≤ *i* ≤ *H*, 1 ≤ *j* ≤ *W* - 1).
*   *B<sub>i,j</sub>* is either 0 or 1 (1 ≤ *i* ≤ *H* - 1, 1 ≤ *j* ≤ *W*).
*   *C<sub>i</sub>* is either 1 or 2 (1 ≤ *i* ≤ *H*).
*   2 ≤ *T<sub>k</sub>* (1 ≤ *k* ≤ *Q*).
*   *T*<sub>1</sub> + *T*<sub>2</sub> + ... + *T<sub>Q</sub>* ≤ 200 000.
*   1 ≤ *X<sub>k,l</sub>* ≤ *H* (1 ≤ *k* ≤ *Q*, 1 ≤ *l* ≤ *T<sub>k</sub>*).
*   1 ≤ *Y<sub>k,l</sub>* ≤ *W* (1 ≤ *k* ≤ *Q*, 1 ≤ *l* ≤ *T<sub>k</sub>*).
*   (*X<sub>k,1</sub>*, *Y<sub>k,1</sub>*), (*X<sub>k,2</sub>*, *Y<sub>k,2</sub>*), ..., (*X<sub>k,Tk</sub>*, *Y<sub>k,Tk</sub>*) are distinct (1 ≤ *k* ≤ *Q*).
*   Given values are all integers.

### Subtasks

1.  (10 points) *C<sub>i</sub>* = 1 (1 ≤ *i* ≤ *H*), *Q* ≤ 5, *T<sub>k</sub>* = 2 (1 ≤ *k* ≤ *Q*), *A<sub>i,j</sub>* = 0 (1 ≤ *i* ≤ *H*, 1 ≤ *j* ≤ *W* - 1).
2.  (6 points) *C<sub>i</sub>* = 1 (1 ≤ *i* ≤ *H*), *Q* ≤ 5, *T<sub>k</sub>* = 2 (1 ≤ *k* ≤ *Q*).
3.  (15 points) *C<sub>i</sub>* = 1 (1 ≤ *i* ≤ *H*), *Q* ≤ 5.
4.  (11 points) *C<sub>i</sub>* = 1 (1 ≤ *i* ≤ *H*), *T<sub>k</sub>* = 2 (1 ≤ *k* ≤ *Q*).
5.  (6 points) *C<sub>i</sub>* = 1 (1 ≤ *i* ≤ *H*).
6.  (12 points) *Q* ≤ 5.
7.  (26 points) *T<sub>k</sub>* = 2 (1 ≤ *k* ≤ *Q*).
8.  (14 points) No additional constraints.

#### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| 4 3 4          | 1              |
| 00             | 3              |
| 00             | 0              |
| 00             | -1             |
| 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            |                |

The figure below shows the current status of the road network. The gray part is closed, and the blue part is passable.

![](_page_3_Figure_5.jpeg)

*   In the first question, a repair with *i* = 2 will make the status of the road network as follows, and intersections (1, 1) and (3, 3) will be mutually connected.

![](_page_4_Picture_3.jpeg)

The period of a repair plan consisting of this single repair is 1 day, and there is no repair plan with a shorter period that makes intersections (1, 1) and (3, 3) mutually reachable, so your program should output 1 in the first line.

*   In the second question, three repairs with *i* = 1, 2, 3 respectively will make the intersection (3, 1) and (1, 2) mutually reachable. The period of a repair plan consisting of these three repairs is 3 days, and there is no repair plan with a shorter period that makes intersections (3, 1) and (1, 2) mutually reachable, so your program should output 3 in the second line.
*   In the third question, the intersections (2, 3) and (3, 3) are already mutually reachable, so your program should output 0 in the third line.
*   In the fourth question, there is no repair plan that makes intersections (4, 2) and (3, 2) mutually reachable, so your program should output -1 in the fourth line.

This sample input satisfies the constraints of Subtasks 1, 2, 3, 4, 5, 6, 7, 8.

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| 4 4 4          | 1              |
| 100            | 3              |
| 110            | 2              |
| 011            | 2              |
| 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            |                |

This sample input satisfies the constraints of Subtasks 2, 3, 4, 5, 6, 7, 8.

| Sample Input 3 | Sample Output 3 |
| :------------- | :------------- |
| 7 3 3          | 3              |
| 10             | 2              |
| 00             | 4              |
| 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            |                |

This sample input satisfies the constraints of Subtasks 3, 5, 6, 8.

| Sample Input 4 | Sample Output 4 |
| :------------- | :------------- |
| 4 3 3          | 1              |
| 00             | 2              |
| 00             | 5              |
| 10             |                |
| 00             |                |
| 110            |                |
| 011            |                |
| 001            |                |
| 1 2 2 2        |                |
| 2              |                |
| 1 1            |                |
| 3 1            |                |
| 2              |                |
| 4 3            |                |
| 2 1            |                |
| 2              |                |
| 4 1            |                |
| 1 3            |                |

This sample input satisfies the constraints of Subtasks 6, 7, 8.

| Sample Input 5 | Sample Output 5 |
| :------------- | :------------- |
| 7 3 2          | 4              |
| 01             | 1              |
| 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            |                |

This sample input satisfies the constraints of Subtasks 6, 8.

Starter code:

Grader code:

Setup script:

Evaluation script: