최단 경로 질의

$W \times H$ 크기의 격자가 주어진다. 각 칸에는 정수가 하나씩 적혀 있다. 왼쪽 위 칸을 $(1, 1)$, 오른쪽 아래 칸을 $(W, H)$라고 한다.

칸 $S$에서 칸 $T$까지의 경로는 칸들의 나열이다. 첫 번째 칸은 $S$, 마지막 칸은 $T$이고, 연속한 두 칸은 변을 공유한다. 경로의 비용은 경로에 포함된 모든 칸의 값의 합이다.

격자에 적힌 정수와 $Q$개의 칸 쌍 $(SX_i, SY_i)$, $(TX_i, TY_i)$가 주어진다. 각 쌍에 대해 칸 $(SX_i, SY_i)$에서 칸 $(TX_i, TY_i)$까지 가는 경로의 최소 비용을 구한다.

첫 줄에 세 정수 $W$, $H$, $Q$가 주어진다 ($1 \le W \le 10$, $2 \le H \le 10^4$, $1 \le Q \le 10^5$).

다음 $H$개의 줄은 격자를 나타낸다. 그중 $y$번째 줄의 $x$번째 수 $A_{x,y}$는 칸 $(x, y)$에 적힌 정수이다 ($0 \le A_{x,y} \le 10^9$).

다음 $Q$개의 줄에는 칸 쌍 $(SX_i, SY_i)$, $(TX_i, TY_i)$가 한 쌍씩 주어진다 ($1 \le SX_i, TX_i \le W$, $1 \le SY_i, TY_i \le H$, $(SX_i, SY_i) \ne (TX_i, TY_i)$).

$Q$개의 줄을 출력한다. $i$번째 줄에는 칸 쌍 $(SX_i, SY_i)$와 $(TX_i, TY_i)$에 대한 최소 비용을 출력한다.