Problem G: 水時計

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

水時計は水平な広い平面上に置かれ、１つ以上の一辺が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

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

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

Output

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

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

Note

Commentary

 

---