시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 2 2 2 100.000%

문제

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 in the sequence is $T$, and any two consecutive cells in the sequence share an edge. The cost of a path is defined as the sum of costs of all cells in the path.

You are given the integers written on the grid, and also $Q$ pairs of cells $(\mathit{SX}_i, \mathit{SY}_i)$, $(\mathit{TX}_i, \mathit{TY}_i)$. For each pair, compute the minimum cost of the path from the cell $(\mathit{SX}_i, \mathit{SY}_i)$ to the cell $(\mathit{TX}_i, \mathit{TY}_i)$.

입력

On the first line, you are given three integers $W$, $H$, and $Q$ ($1 \le W \le 10$, $2 \le H \le 10^4$, $1 \le Q \le 10^5$).

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

On the next $Q$ lines, you are given pairs of cells $(\mathit{SX}_i, \mathit{SY}_i)$, $(\mathit{TX}_i, \mathit{TY}_i)$ ($1 \le \mathit{SX}_i, \mathit{TX}_i \le W$, $1 \le \mathit{SY}_i, \mathit{TY}_i \le H$, $(\mathit{SX}_i, \mathit{SY}_i) \ne (\mathit{TX}_i, \mathit{TY}_i)$).

출력

Print $Q$ lines. On the $i$-th line, print the answer for the pair $(\mathit{SX}_i, \mathit{SY}_i)$ and $(\mathit{TX}_i, \mathit{TY}_i)$.

예제 입력 1

2 5 4
0 1
0 1
0 0
1 0
1 0
1 1 2 5
2 1 1 5
1 3 2 3
1 5 1 1

예제 출력 1

0
2
0
1

예제 입력 2

3 6 5
1 9 2
3 4 1
2 5 3
4 2 2
3 1 5
2 6 3
1 1 3 1
1 1 3 6
1 6 3 6
1 3 3 4
2 6 3 2

예제 출력 2

11
21
11
10
15