問題文

E869120 君の家は、$H$ 行 $W$ 列のマス目で表されます。上から $i$ 行目、左から $j$ 列目をマス $(i, j)$ とします。左上のマスは $(1, 1)$、右下のマスは $(H, W)$ です。
彼の家において、マス $(i, j)$ の動きにくさの値は　$A_{i, j}$ です。
彼は上下左右に隣り合うマスを介して家の中を移動することが出来ます。

さて、レベル $K$ の災害が発生した時、E869120 君がマスを移動するのに以下のような時間がかかります。

• 彼がマス $(i_1, j_1)$, $(i_2, j_2)$, $(i_3, j_3)$, ..., $(i_G, j_G)$ を順に通ったとする。（開始位置と終了位置も含める）
• その時、移動に $(K^2+A_{i_1,j_1}) + (K^2+A_{i_2,j_2}) + (K^2+A_{i_3,j_3}) + ... + (K^2+A_{i_G,j_G})$ 秒かかる。
• 彼は同じマスを二度通ることが出来ない。

• マス $(x_i, y_i)$ に E869120 君がいるときにレベル $k_i$ の災害が発生した。非常用出口のマスにたどり着き脱出するまでに何秒かかるか？

制約

全ての入力データは以下の制約を満たします。

• $H$ は $1$ 以上 $250$ 以下の整数である
• $W$ は $1$ 以上 $250$ 以下の整数である
• $Q$ は $1$ 以上 $500 \ 000$ 以下の整数である
• $A_{i, j}$ は $1$ 以上 $99$ 以下の整数である
• $x_i$ は $1$ 以上 $H$ 以下の整数である
• $y_i$ は $1$ 以上 $W$ 以下の整数である
• $k_i$ は $1$ 以上 $1 \ 000 \ 000$ 以下の整数である
• $gx$ は $1$ 以上 $H$ 以下の整数である
• $gy$ は $1$ 以上 $W$ 以下の整数である

入力

$H$ $W$
$gx$ $gy$
$A_{1, 1}$ $A_{1, 2}$ $A_{1, 3}$ ... $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $A_{2, 3}$ ... $A_{2, W}$
$A_{3, 1}$ $A_{3, 2}$ $A_{3, 3}$ ... $A_{3, W}$
...
$A_{H, 1}$ $A_{H, 2}$ $A_{H, 3}$ ... $A_{H, W}$
$Q$
$x_1$ $y_1$ $k_1$
$x_2$ $y_2$ $k_2$
$x_3$ $y_3$ $k_3$
...
$x_Q$ $y_Q$ $k_Q$

出力

$Q$ 行に渡って出力してください。
$i$ 行目には、$i$ 回目のクエリに対する答えを出力してください。

サンプル

4 5
1 1
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4
5
3 1 1
1 1 7
4 5 3
3 2 5
3 5 2

20
52
102
114
54

7 7
7 3
1 1 1 1 1 1 1
99 99 99 99 99 99 1
99 1 1 1 1 1 1
99 1 99 99 99 99 99
99 1 1 1 1 1 99
99 99 99 99 99 1 99
99 99 1 1 1 1 99
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10

50
125
248
349
430
529
646
781
934
1105

7 7
7 6
1 1 1 1 1 1 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 9 1
9 9 9 9 9 1 1
2
1 1 4
1 1 5

238
352