AT_bogosortcontest_div1_c Moving Silver

縦 $ H $ 行、横 $ W $ 列の盤面があります。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,j) $ と呼びます。マス $ (i,j) $ には整数 $ A_{i,j} $ が書かれています。 $ Q $ 個のクエリが与えられます。 各クエリでは整数 $ X,Y,N $ が与えられるので、以下の問題を解いてください。なお、各クエリは独立です。 > はじめに、マス $ (X,Y) $ に将棋の駒の「銀」を $ 1 $ 枚置きます。 > > 銀は常に盤面の上方向を前とします。すなわち、銀がマス $ (i,j) $ にあるとき、以下のマスのうち盤面内にあるマスへ移動できます。 > > - $ (i-1,j-1) $ > - $ (i-1,j) $ > - $ (i-1,j+1) $ > - $ (i+1,j-1) $ > - $ (i+1,j+1) $ > > 銀の向きは、移動や手番によって変化しません。 > > Alice と Bob は Alice を先手として交互に銀を動かし、ちょうど $ N $ 回の移動を行います。各手番では、銀を移動可能なマスのうちいずれか $ 1 $ つへ移動させます。 > > $ N $ 回の移動を行った後に銀がマス $ (i,j) $ にあるとき、スコアを $ A_{i,j} $ とします。 > > Alice はスコアを最大化し、Bob はスコアを最小化するように、それぞれ最善を尽くします。 > > 両者が最善を尽くしたときのスコアを求めてください。

入力は以下の形式で標準入力から与えられる。ここで、 $ X_i, Y_i, N_i $ は $ i $ 番目のクエリで与えられる $ X, Y, N $ を表す。 > $ H $ $ W $ $ A_{1,1} $ $ A_{1,2} $ $ \ldots $ $ A_{1,W} $ $ A_{2,1} $ $ A_{2,2} $ $ \ldots $ $ A_{2,W} $ $ \vdots $ $ A_{H,1} $ $ A_{H,2} $ $ \ldots $ $ A_{H,W} $ $ Q $ $ X_1 $ $ Y_1 $ $ N_1 $ $ X_2 $ $ Y_2 $ $ N_2 $ $ \vdots $ $ X_Q $ $ Y_Q $ $ N_Q $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリの答えを整数として出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリでは、はじめ銀はマス $ (2,2) $ にあります。 Alice は銀を - マス $ (1,1) $ - マス $ (1,2) $ - マス $ (1,3) $ - マス $ (3,1) $ - マス $ (3,3) $ のいずれかに移動できます。それぞれのマスに書かれている整数は $ 2,9,4,6,8 $ なので、Alice はマス $ (1,2) $ に銀を移動することでスコアを $ 9 $ にできます。したがって、このクエリの答えは $ 9 $ です。 $ 2 $ 番目のクエリでは、はじめ銀はマス $ (2,2) $ にあり、Alice と Bob が $ 1 $ 回ずつ銀を動かします。 例えば、Alice が最初にマス $ (1,1) $ に銀を移動すると、Bob はマス $ (2,2) $ に銀を移動するしかないため、スコアは $ 5 $ になります。 Alice はスコアを $ 5 $ 以上にすることを保証できます。一方、Alice がどのように銀を動かしても、Bob はスコアを $ 5 $ 以下にすることができます。したがって、このクエリの答えは $ 5 $ です。 ### Constraints - $ 2 \le H, W \le 600 $ - $ HW \le 10^5 $ - $ -10^9 \le A_{i, j} \le 10^9 $ - $ 1 \le Q \le 2\times 10^5 $ - $ 1 \le X_i \le H $ - $ 1 \le Y_i \le W $ - $ 1 \le N_i \le 10^{18} $ - 入力される数値はすべて整数