最短路クエリ
题意翻译
## 题目描述
在$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$。
接下来的$H$行，每行$M$个数，其中第$x$行第$y$列的数表示棋盘上格子$(x,y)$上标的数$A_{x,y}$。
再下面最后的$Q$行，每行4个数，表示数对$(SX_i,SY_i)$，$(TX_i,TY_i)$。
### 输出格式：
共$Q$行，输出各格子对之间的最短路径。即，在第$i$行中，输出从$(SX_i,SY_i)$到$(TX_i,TY_i)$的最短路径的长度。
## 数据限制
对 100% 的数据有
$1\le W\le 10$
$2\le H\le 10^4$
$1\le Q\le 10^5$
$0\le A_{x,y}\le 10^9$
$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)$
## 部分分
这个问题的评测中，设置了50分的部分分，即对50%的数据点，有$W\le 2$。
## 样例
#### 输入样例#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
题目描述
[problemUrl]: https://atcoder.jp/contests/utpc2012/tasks/utpc2012_09