問題

W \times H のグリッド状に区切られた盤面があり，各マスには数字が書かれている．左上のマスを (1, 1)，右下のマスを (W, H) と表す．

マス S からマス T への経路とは，マスの列であって，最初と最後が S と T であり，かつ列において連続する任意の 2 つのマスは隣接しているようなものである．ここで，隣接するとは，辺を共有することを指す．経路のコストとは，経路に含まれるマスに書かれている数字の合計である．

盤面に書かれた数字と Q 個のマスの対が与えられたとき，各マスの対 (SX_i, SY_i), (TX_i, TY_i) に対し，マス (SX_i, SY_i) からマス (TX_i, TY_i) への経路のコストの最小値を答えるプログラムを出力せよ．

---

入力

W H Q
A_{1,1} A_{2,1} ... A_{W,1}
...
A_{1,H} A_{2,H} ... A_{W,H}
SX_1 SY_1 TX_1 TY_1
...
SX_Q SY_Q TX_Q TY_Q

入力の最初の行には，縦幅 H と横幅 W とクエリの個数 Q が与えられる.

続く H 行には，盤面に書かれている数字が与えられる． y 行目の x 個目の数字 A_{x,y} はマス (x, y) に書かれた数字である．

さらに続く Q 行に，マスの対 (SX_i, SY_i), (TX_i, TY_i) が書かれている．

出力

各行に，各マスの対に対する経路のコストの最小値を出力せよ． 即ち，i 行目に，マス (SX_i, SY_i) からマス (TX_i, TY_i) への経路のコストの最小値を出力せよ．

制約

• 1 \leq W \leq 10
• 2 \leq H \leq 10^4
• 1 \leq Q \leq 10^5
• 0 \leq A_{x,y} \leq 10^9
• 1 \leq SX_i, TX_i \leq W
• 1 \leq SY_i, TY_i \leq H
• (SX_i, SY_i) \neq (TX_i, TY_i)

部分点

この問題の判定には，50 点分のテストケースのグループが設定されている． このグループに含まれるテストケースの入力は追加で以下の条件を満たす．

• W=2 W \leq 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