AT_utpc2012_09 最短路クエリ

在 $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)$ 的最短路径的长度。

对 $50\%$ 的数据，有 $W \le 2$。 对 $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) \neq (TX_i, TY_i)$