给定一个 $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) \neq (TX_i, TY_i)$)。

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 对单元格 $(SX_i, SY_i)$ 和 $(TX_i, 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