問題文

$H$ 行 $W$ 列のグリッドがあります。このグリッドの上から $i$ 行目、左から $j$ 列目のマス目を $(i,j)$ と書きます。 マス$(i,j)$ には正の整数 $A_{i,j}$ が書かれています。

上下左右に隣接するマス目に移動することを繰り返して $(rs, cs)$ から $(rt, ct)$ まで移動する経路の コスト を 経路上（両端のマスを含む）に書かれたすべての整数の最大値と定義します。

$x = 1, 2, \ldots, Q$ について、以下の問題に答えてください。

• 上下左右に隣接するマス目に移動することを繰り返して $(rs_x, cs_x)$ から $(rt_x, ct_x)$ まで移動するすべての経路のうち、 コストが最小となるもののコストを出力せよ。

入力

$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\cdots$ $A_{H,W}$
$Q$
$rs_1$ $cs_1$ $rt_1$ $ct_1$
$rs_2$ $cs_2$ $rt_2$ $ct_2$
$\vdots$
$rs_Q$ $cs_Q$ $rt_Q$ $ct_Q$

• $2 \le H,W \le 500$
• $1 \le A_{i,j} \le H\times W \quad (1 \le i \le H, 1 \le j \le W)$
• $1 \le Q \le 2\times 10^5$
• $1 \le rs_i, rt_i \le H \quad (1 \le i \le Q)$
• $1 \le cs_i, ct_i \le W \quad (1 \le i \le Q)$
• $(rs_i, cs_i) \neq (rt_i, ct_i) \quad (1 \le i \le Q)$

出力

$Q$ 行出力せよ。$i$ 行目には $x = i$ に対する問題の答えを出力をせよ。

サンプル

3 4
1 5 3 2
3 4 3 2
3 2 3 5
2
1 1 3 4
1 1 2 3

5
3

7 5
12 6 18 9 11
10 33 34 35 27
15 6 3 34 33
5 25 15 8 16
23 11 18 6 32
13 25 17 2 7
28 13 3 18 35
5
5 1 2 2
1 5 1 1
1 5 6 5
1 1 7 2
6 5 2 4

33
18
18
17
35