Road Service 2

JOI 시에는 무한히 긴 동서 방향 도로 $H$개와 무한히 긴 남북 방향 도로 $W$개로 이루어진 격자 모양의 도로망이 있다. 교차점 $(i, j)$ ($1 \le i \le H$, $1 \le j \le W$)는 북쪽에서 $i$번째 동서 도로와 서쪽에서 $j$번째 남북 도로가 만나는 지점이다.

도로 상태가 좋지 않아 일부 도로는 막혀 있다.

• 북쪽에서 $i$번째 동서 도로에서 교차점 $(i, j)$와 $(i, j + 1)$을 잇는 구간 ($1 \le j \le W - 1$)은 $A_{i, j} = 0$이면 막혀 있고, $A_{i, j} = 1$이면 통행할 수 있다.
• 서쪽에서 $j$번째 남북 도로에서 교차점 $(i, j)$와 $(i + 1, j)$를 잇는 구간 ($1 \le i \le H - 1$)은 $B_{i, j} = 0$이면 막혀 있고, $B_{i, j} = 1$이면 통행할 수 있다.
• 나머지 도로 구간 (격자 교차점 바깥 부분)은 모두 막혀 있다.

JOI 시장 K는 도로망의 보수 계획을 세우고 있다. 보수 계획은 0회 이상의 보수로 이루어진다. 보수는 $1 \le i \le H$를 만족하는 정수 $i$를 골라 다음을 수행하는 것이다.

모든 정수 $j$ ($1 \le j \le W - 1$)에 대해, 북쪽에서 $i$번째 동서 도로의 교차점 $(i, j)$와 $(i, j + 1)$을 잇는 구간이 막혀 있으면 통행할 수 있게 만든다.

보수 하나에는 $C_i$일이 걸린다. $C_i$는 $1$ 또는 $2$이다. 보수는 동시에 진행할 수 없으므로, 보수 계획의 기간은 계획에 포함된 보수들에 걸린 날짜의 합이다.

K 시장은 도시 시설 사이의 경로를 확보하는 일을 중요하게 여기며 $Q$개의 질문을 한다. $k$번째 질문은 다음과 같다.

$T_k$개의 교차점 $(X_{k,1}, Y_{k,1}), (X_{k,2}, Y_{k,2}), \dots, (X_{k,T_k}, Y_{k,T_k})$를 서로 도달 가능하게 만드는 보수 계획이 있는가? 있다면 그러한 계획의 기간 최솟값은 얼마인가?

도로 상태, 동서 도로별 보수 일수, 그리고 질문 내용이 주어졌을 때 모든 질문에 답하는 프로그램을 작성하라.

입력은 다음 형식으로 주어진다.

H W Q
A_{1,1}A_{1,2} ... A_{1,W-1}
A_{2,1}A_{2,2} ... A_{2,W-1}
...
A_{H,1}A_{H,2} ... A_{H,W-1}
B_{1,1}B_{1,2} ... B_{1,W}
B_{2,1}B_{2,2} ... B_{2,W}
...
B_{H-1,1}B_{H-1,2} ... B_{H-1,W}
C_1 C_2 ... C_H
Query_1
Query_2
...
Query_Q

각 $Query_k$는 다음 형식이다.

T_k
X_{k,1} Y_{k,1}
X_{k,2} Y_{k,2}
...
X_{k,T_k} Y_{k,T_k}

$Q$개의 줄을 출력한다. $k$번째 줄에는 $T_k$개의 교차점을 서로 도달 가능하게 만드는 보수 계획 기간의 최솟값을 출력한다. 그런 계획이 없으면 $-1$을 출력한다.

• $2 \le H$, $2 \le W$, $H \times W \le 1{,}000{,}000$.
• $1 \le Q \le 100{,}000$, $T_1 + T_2 + \cdots + T_Q \le 200{,}000$.
• 모든 $k$에 대해 $2 \le T_k$.
• 각 $A_{i,j}$와 $B_{i,j}$는 $0$ 또는 $1$이다.
• 각 $C_i$는 $1$ 또는 $2$이다.
• $1 \le X_{k,l} \le H$, $1 \le Y_{k,l} \le W$.
• 각 질문의 $T_k$개 교차점은 서로 다르다.
• 주어지는 값은 모두 정수이다.