/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
縦 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 はスコアを最小化するように、それぞれ最善を尽くします。
両者が最善を尽くしたときのスコアを求めてください。
制約
- 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}
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ここで、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 番目のクエリの答えを整数として出力せよ。
入力例 1
3 3 2 9 4 7 5 3 6 1 8 4 2 2 1 2 2 2 2 2 3 1 1 5
出力例 1
9 5 9 5
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 です。
入力例 2
2 2 1000000000 1000000000 -1000000000 -1000000000 1 1 1 1000000000000000000
出力例 2
1000000000
入力例 3
8 8 1011111 1111111 1111111 1111111 1111111 1111111 1111111 1110111 1011111 1111111 1111111 1111111 1111111 1111111 1111111 1110111 1000011 1100011 1100001 1100011 1100001 1100011 1011001 1000001 1011101 1011101 1011101 1011101 1011111 1011101 1001111 1110111 1011101 1011101 1011101 1011101 1100011 1011101 1011111 1110111 1011101 1011101 1100001 1011101 1111101 1011101 1011111 1110111 1000011 1100011 1111101 1100011 1000011 1100011 1011111 1110111 1111111 1111111 1000011 1111111 1111111 1111111 1111111 1111111 15 1 1 2982558278264656 4 1 681035882507799922 4 2 655197505087209540 3 1 944345619717877850 7 6 247886070908114434 7 7 525221092584163358 7 8 918056333412056838 1 4 943113313864585689 4 3 256528106730450573 5 6 7736679867786292 7 6 97011565420390018 7 7 594086481306962232 7 8 485673926704995108 6 3 181743627914139642 8 5 48001317691504937
出力例 3
1000011 1011101 1011101 1000011 1011111 1011111 1011111 1111111 1100011 1011101 1011111 1011111 1011111 1011101 1100011