琵琶湖の湖底から変わった形の水時計のようなものが発見された。
水時計は水平な広い平面上に置かれ、1つ以上の一辺が30cmの立方体の水槽で構成されている。 水槽は格子状に並べられた様々な高さの台の上に置かれている。水槽の厚みは無視できる。 同じ高さの台の上に置かれた水槽が前後左右に隣接していたとき、それらの水槽の間には穴があけられ、水の高さが等しく保たれる仕組みになっている。(図1)
|
一緒に発見された文献によると、ある水槽に水を継続的に注ぎ、他の特定の水槽の水位を調べていたらしい。
図2のようにある水槽に水を注ぎ、水があふれたとき、あふれた水はその水槽に隣接している方向に等しい量流れ込む。水槽がない場所に水が流れた場合、水時計の外に自動的に排水される。 また水があふれる方向がなくとも、水槽の容量より多い水が格子内にとどまることはない。そのような場合、水槽の容量を超えた分の水は不思議な力で消滅する。 隣接している水槽が、もとの水槽より少しでも高い台に置かれていたとき、その方向に水は流れないので注意すること。 例えば図3の場合、中央の水槽から左右と奥の水槽にそれぞれあふれた量の1/4ずつの水が流れ込む。
|
|
あなたの仕事はこの水時計をシミュレートするプログラムを書く事である。
入力は複数のデータセットからなる。 データセットの個数は、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を満たす。 fx、fy、fqは水を流す水槽が置いている格子の場所(fx、fy)と流量(fq)を表す。流量の単位はcm^3である。 これらは0 ≤ fx < w、0 ≤ fy < h、1 ≤ fq ≤ 30000を満たす。 続くh行はそれぞれスペースで区切られたw個の数字から構成されており、 格子{i,j}に置ける水槽の置かれた台の高さを表す。 単位はcmであり、0 ≤ pi,j ≤ 1000を満たす整数である。 pi,j=0のとき、その場所には水槽は置かれていない。 次の一行は水槽の水の高さの測定回数を表す正の整数lからなる。 これは1 ≤ l ≤ 10を満たす。 続くl行はスペースで区切られたtk、xk、ykの3つの整数値を含んでいる。 tkは測定時間を表し、xk、ykは測定場所の格子を示す。 xk、ykは必ず水槽のある格子を示すと仮定してよい。 また、0 ≤ t ≤ 10000を満たす。
入力の終わりはふたつのゼロを含む行で表される。
各データセットに対し、整数をl個出力する。 その整数は指定された時間tkにおける 格子xk、yk上にある水槽の水の高さを出力すること。 なお、水の高さの小数点以下は切り捨てとする。
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
5 5 8 30 5 13 4