Shortest Path Queries

You are given a $W \times H$ grid. Each cell contains an integer. The top-left cell is called $(1, 1)$, and the bottom-right cell is called $(W, H)$.

A path from a cell $S$ to a cell $T$ is a sequence of cells such that the first cell in the sequence is $S$, the last cell is $T$, and any two consecutive cells share an edge. The cost of a path is the sum of the costs of all cells in the path.

You are given the integers written in the grid and $Q$ pairs of cells $(SX_i, SY_i)$ and $(TX_i, TY_i)$. For each pair, compute the minimum cost of a path from cell $(SX_i, SY_i)$ to cell $(TX_i, TY_i)$.

The first line contains three integers $W$, $H$, and $Q$ ($1 \le W \le 10$, $2 \le H \le 10^4$, $1 \le Q \le 10^5$).

The next $H$ lines describe the grid. The $x$-th number on the $y$-th of these lines, $A_{x,y}$, is the integer written in cell $(x, y)$ ($0 \le A_{x,y} \le 10^9$).

The next $Q$ lines each contain a pair of cells $(SX_i, SY_i)$ and $(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)$).

Print $Q$ lines. On the $i$-th line, print the minimum cost for the pair $(SX_i, SY_i)$ and $(TX_i, TY_i)$.