문제
JOI 도시에는 무한히 긴 동서 방향 도로 H개와 무한히 긴 남북 방향 도로 W개로 구성된 격자형 도로망이 있습니다. 교차점 (i, j) (1 ≤ i ≤ H, 1 ≤ j ≤ W)은 북쪽에서 i번째 동서 방향 도로와 서쪽에서 j번째 남북 방향 도로가 교차하는 지점입니다.
현재 도로 상태가 좋지 않아 일부 도로가 폐쇄되었습니다. 구체적으로, 도로 상태는 다음과 같습니다:
북쪽에서 i번째 동서 방향 도로 (1 ≤ i ≤ H)에서 교차점 (i, j)와 교차점 (i, j + 1) (1 ≤ j ≤ W − 1)을 연결하는 도로 구간은 Ai,j = 0일 때 폐쇄되고, Ai,j = 1일 때 통행 가능합니다.
서쪽에서 j번째 남북 방향 도로 (1 ≤ j ≤ W)에서 교차점 (i, j)와 교차점 (i + 1, j) (1 ≤ i ≤ H − 1)을 연결하는 도로 구간은 Bi,j = 0일 때 폐쇄되고, Bi,j = 1일 때 통행 가능합니다.
H × W 교차점 이외의 도로는 모두 폐쇄되었습니다.
JOI 도시의 시장인 K 대통령은 도로망 수리 계획을 세우기로 했습니다. 수리 계획은 하나 이상의 수리로 구성됩니다. 수리는 1 ≤ i ≤ H를 만족하는 정수 i를 선택하여 다음 작업을 수행하는 것입니다:
1 ≤ j ≤ W − 1를 만족하는 모든 정수 j에 대해, 북쪽에서 i번째 동서 방향 도로에서 교차점 (i, j)와 교차점 (i, j + 1)을 연결하는 구간을 통행 가능하게 만듭니다 (폐쇄된 경우).
이 수리는 Ci일이 걸리며, Ci는 1 또는 2 중 하나입니다.
수리 계획은 동시에 수행될 수 없으므로, 수리 계획의 기간은 수리에 소요되는 시간의 합과 동일합니다.
K 대통령은 도시 시설 간 경로 확보가 중요하다고 생각하여 여러분에게 Q개의 질문을 했습니다. k번째 질문 (1 ≤ k ≤ Q)은 다음과 같습니다:
주어진 Tk개의 교차점 (Xk,1, Yk,1), (Xk,2, Yk,2), ..., (Xk,Tk, Yk,Tk)를 서로 도달 가능하게 만드는 수리 계획이 존재합니까? 그렇다면, 그러한 수리 계획의 최소 기간은 몇 일입니까?
도로망 상태, 각 동서 방향 도로의 수리에 소요되는 시간, K 대통령의 질문 내용을 입력받아 모든 질문에 답하는 프로그램을 작성하세요.
입력
표준 입력에서 다음 데이터를 읽습니다.
첫 번째 줄:
H, W, Q 다음
H 줄:A_{i,1}, A_{i,2}, ..., A_{i,W−1} (각 줄에W−1 개의 숫자)다음
H−1 줄:B_{i,1}, B_{i,2}, ..., B_{i,W} (각 줄에W 개의 숫자)다음
H 줄:C_1, C_2, ..., C_H (각 줄에 1 또는 2)다음
Q 줄: 각 질문에 대한T_k , 그 뒤로T_k 개의X_{k,l}, Y_{k,l} (각 줄에T_k 개의 쌍)
[제약 조건]
2 ≤ H 2 ≤ W H × W ≤ 1,000,000 1 ≤ Q ≤ 100,000 A_{i,j} 와B_{i,j} 는 0 또는 1C_i 는 1 또는 22 ≤ T_k\ (1 \le k \le Q) T_1 + T_2 + ... + T_Q ≤ 200,000 1 ≤ X_{k,l} ≤ H 1 ≤ Y_{k,l} ≤ W 각 질문에서 주어진 교차점 쌍은 서로 다릅니다.
모든 값은 정수입니다.
출력
표준 출력으로 Q줄을 출력합니다. 각 줄에, k번째 질문에 대해 주어진 교차점들이 서로 도달 가능하게 만드는 최소 기간을 출력합니다. 그러한 수리 계획이 존재하지 않는 경우, -1을 출력하세요.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | Ci = 1 (1 ≤ i ≤ H)，Q ≤ 5，Tk = 2 (1 ≤ k ≤ Q)，Ai, j = 0 (1 ≤ i ≤ H, 1 ≤ j ≤ W − 1). |
| #2 | 6점 | Ci = 1 (1 ≤ i ≤ H)，Q ≤ 5，Tk = 2 (1 ≤ k ≤ Q). |
| #3 | 15점 | Ci = 1 (1 ≤ i ≤ H)，Q ≤ 5. |
| #4 | 11점 | Ci = 1 (1 ≤ i ≤ H)，Tk = 2 (1 ≤ k ≤ Q). |
| #5 | 6점 | Ci = 1 (1 ≤ i ≤ H) |
| #6 | 12점 | Q ≤ 5 |
| #7 | 26점 | Tk = 2 (1 ≤ k ≤ Q) |
| #8 | 14점 | 추가 제약 조건 없음 |
예제1
434
00
00
00
00
100
001
000
1111
2
11
33
2
31
12
2
23
33
2
42
32
1
3
0
-1
예제2
444
100
110
011
010
0010
1001
0101
1111
2
12
31
2
14
41
2
32
12
2
43
11
1
3
2
2
예제3
733
10
00
00
10
00
01
00
110
101
011
001
110
100
1111111
3
72
31
32
3
31
63
23
7
22
13
73
52
12
72
31
3
2
4
예제4
433
00
00
10
00
110
011
001
1222
2
11
31
2
43
21
2
41
13
1
2
5
예제5
732
01
00
00
00
00
10
01
100
110
011
001
101
001
1121122
3
72
13
51
5
11
22
31
23
42
4
1