Water Clock

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem G: 水時計

琵琶湖の湖底から変わった形の水時計のようなものが発見された。

水時計は水平な広い平面上に置かれ、1つ以上の一辺が30cmの立方体の水槽で構成されている。 水槽は格子状に並べられた様々な高さの台の上に置かれている。水槽の厚みは無視できる。 同じ高さの台の上に置かれた水槽が前後左右に隣接していたとき、それらの水槽の間には穴があけられ、水の高さが等しく保たれる仕組みになっている。(図1)

図1

一緒に発見された文献によると、ある水槽に水を継続的に注ぎ、他の特定の水槽の水位を調べていたらしい。

図2のようにある水槽に水を注ぎ、水があふれたとき、あふれた水はその水槽に隣接している方向に等しい量流れ込む。水槽がない場所に水が流れた場合、水時計の外に自動的に排水される。 また水があふれる方向がなくとも、水槽の容量より多い水が格子内にとどまることはない。そのような場合、水槽の容量を超えた分の水は不思議な力で消滅する。 隣接している水槽が、もとの水槽より少しでも高い台に置かれていたとき、その方向に水は流れないので注意すること。 例えば図3の場合、中央の水槽から左右と奥の水槽にそれぞれあふれた量の1/4ずつの水が流れ込む。

図2
図3

あなたの仕事はこの水時計をシミュレートするプログラムを書く事である。

Input

入力は複数のデータセットからなる。 データセットの個数は、300以下で、それぞれが以下の形式である。

w h
fx fy fq
p0,0 p0,1 ... p0,w-1
p1,0 p1,1 ... p1,w-1
...
ph-1,0 ph-1,1 ... ph-1,w-1
l
t1 x1 y1
...
tl xl yl

whは、それぞれ格子の列および行の数を表す正の整数であり、それぞれ1 ≤ w ≤ 101 ≤ h ≤ 10を満たす。 fxfyfqは水を流す水槽が置いている格子の場所(fxfy)と流量(fq)を表す。流量の単位はcm^3である。 これらは0 ≤ fx < w0 ≤ fy < h1 ≤ fq ≤ 30000を満たす。 続くh行はそれぞれスペースで区切られたw個の数字から構成されており、 格子{i,j}に置ける水槽の置かれた台の高さを表す。 単位はcmであり、0 ≤ pi,j ≤ 1000を満たす整数である。 pi,j=0のとき、その場所には水槽は置かれていない。 次の一行は水槽の水の高さの測定回数を表す正の整数lからなる。 これは1 ≤ l ≤ 10を満たす。 続くl行はスペースで区切られたtkxkykの3つの整数値を含んでいる。 tkは測定時間を表し、xkykは測定場所の格子を示す。 xkykは必ず水槽のある格子を示すと仮定してよい。 また、0 ≤ t ≤ 10000を満たす。

入力の終わりはふたつのゼロを含む行で表される。

Output

各データセットに対し、整数をl個出力する。 その整数は指定された時間tkにおける 格子xkyk上にある水槽の水の高さを出力すること。 なお、水の高さの小数点以下は切り捨てとする。

Sample Input

3 3
1 1 900
0 10 0
10 45 10
10 0 0
3
5 1 1
50 1 0
100 0 1
5 5
2 0 9000
0 0 4 0 0
0 3 3 3 0
2 2 2 2 2
0 0 1 0 0
0 0 1 0 0
4
5 2 0
10 2 1
100 2 2
250 2 3
0 0

Output for Sample Input

5
5
8
30
5
13
4

Source: Ritsumeikan University Programming Contest 2011 , Japan, 2011-10-05