メダカのジョンはメダカたちのリーダーである。 最近ジョンはある問題を抱えていた。 ジョンは池の中にメダカたちの新しい街をつくろうと計画していた。 街には当然子供たちが通う学校が必要になるのだが、池にはメダカたちの天敵もいて安全ではない場所も存在している。 ジョンは子供達のために最も安全な場所に学校を建てたいと考えていた。
ジョンがいくつかの建設会社にお願いをして街の開発計画案を求めたところ、現在 q 個の案が集まった。 どの案を選ぶかは投票によって決まる。しかしそれぞれの案について学校を建てるべき最も安全な場所は事前に決めておく必要がある。
池は r*c の２次元グリッドで表される。 グリッドは r 行 ｃ 列で構成されており、左上の座標が (0,0) で右下の座標は r-1 行, c-1 列目で (r-1,c-1) と表す。 二次元グリッドにはそれぞれ危険度が整数値で与えられている。 危険度の値が低い場所ほど安全である。 q 個の案はそれぞれ左上を (r1,c1)、右下を (r2,c2) とするグリッドとして与えられる。
あなたの仕事は r*c のグリッドと q 個の開発案 (r1,c1) , (r2,c2) が与えられるので、それぞれの開発案について、学校を建てるべき場所の危険度を調べることである。 つまりサブグリッド内の最小の値を求めて欲しい。
入力は複数のケースからなる。
各入力は以下の形式で与えられる。
r c q grid0,0 grid0,1 … grid0,c-1 … gridr-1,0 … gridr-1,c-1 r1 c1 r2 c2 ... r1 c1 r2 c2
入力の最初の行は r , c , q の3つの整数からなる。 その後 r 行にそれぞれ c 個の整数が与えられる。 gridi,j は i 行 j 列目の危険度を表す。 また0 ≤ gridi,j ≤ 231-1である。 そのあとに4つの整数 r1 c1 r2 c2からなる q 個のクエリーが与えられる。
入力データは以下の制約を満たす。
r*c ≤ 106
q ≤ 104
r1 ≤ r2, c1 ≤ c2 である。
r * c ≤ 250000 以下なら q ≤ 100であることが保証される。
r * c > 250000 となる場合、入力はそのケースのみであることが保証される。
各クエリーについて最も危険度が低い場所の値を1行に出力せよ。
3 3 4 1 2 3 4 2 2 2 1 1 0 0 2 2 0 0 1 1 1 0 1 0 0 1 1 2 1 10 4 1 2 3 4 5 6 7 8 9 10 0 0 0 9 0 0 0 4 0 5 0 9 0 4 0 5 0 0 0
1 1 4 2 1 1 6 5