왕국 여행

콰드라도니아 왕국은 $R$개의 행과 $C$개의 열로 이루어진 격자로 나뉘어 있고, 칸 하나가 주 하나다. 길이 위험해서 혼자 다니는 사람은 없다. 이동은 모두 호위 마차로 하고, 마차는 주간통신여행회사(ICPC)가 운영한다.

요금 체계는 이렇다. $i$행 $j$열의 주에서는 비용 $V_{ij}$를 내고 마차를 빌린다. 이 마차는 $i$행에서 최대 $R_{ij}$행, $j$열에서 최대 $C_{ij}$열 떨어진 주까지 데려다준다. 즉 $|i - i'| \le R_{ij}$이고 $|j - j'| \le C_{ij}$인 $i'$행 $j'$열의 주에 내릴 수 있다. 요금은 정액이라서 내리는 곳과 무관하고 빌리는 주에서만 정해진다.

당신은 주 $N$개 $p_1, p_2, \dots, p_N$을 이 순서대로 방문하려고 한다. 예산이 빠듯하니 각 구간을 가장 싸게 가는 방법을 알고 싶다. 한 구간에서 중간에 거치는 주의 수에는 제한이 없고, 마차를 빌리는 주마다 그 주의 요금을 낸다.

첫째 줄에 정수 $R$, $C$, $N$이 주어진다 ($1 \le R, C \le 500$, $2 \le N \le 5$). 각각 행의 수, 열의 수, 방문할 주의 수다. 행에는 1번부터 $R$번까지, 열에는 1번부터 $C$번까지 번호가 붙어 있다.

다음 $3 \times R$개의 줄은 $R$줄씩 세 묶음으로 나뉘고, 각 줄에는 정수가 $C$개씩 있다. 첫 묶음의 $i$번째 줄에서 $j$번째 수는 $V_{ij}$다 ($1 \le V_{ij} \le 1000$). 둘째 묶음은 같은 배치로 $R_{ij}$를 ($0 \le R_{ij} \le R$), 셋째 묶음은 $C_{ij}$를 준다 ($0 \le C_{ij} \le C$).

마지막 $N$개의 줄은 방문 순서대로 $p_1, p_2, \dots, p_N$을 나타낸다. $k$번째 줄에는 정수 $I_k$와 $J_k$가 있고 ($1 \le I_k \le R$, $1 \le J_k \le C$), $p_k$가 $I_k$행 $J_k$열의 주라는 뜻이다.

한 줄에 정수 $N - 1$개를 공백 하나로 구분해 출력한다. $k = 1, 2, \dots, N - 1$에 대해 $k$번째 수는 호위 마차로 $p_k$에서 $p_{k+1}$까지 가는 최소 요금 합이고, 그 구간을 갈 수 없으면 $-1$이다. $p_k$와 $p_{k+1}$이 같은 주면 요금은 0이다.