Problem: Problem G: Water clock

An unusually shaped water clock was discovered from the bottom of Lake Biwa.

The water clock is placed on a wide horizontal plane and consists of a cubic aquarium with one or more sides of 30 cm. The aquariums are placed on pedestals of various heights arranged in a grid pattern. The thickness of the aquarium is negligible. When water tanks placed on a table of the same height are adjacent to each other in the front, back, left and right, holes are made between the water tanks to keep the water heights equal. (Figure 1)

<image>
---
Figure 1

According to the literature found together, water was continuously poured into one aquarium to check the water level in another particular aquarium.

When water is poured into an aquarium as shown in Fig. 2 and the water overflows, the overflowed water flows in the same amount in the direction adjacent to the aquarium. If water flows to a place where there is no water tank, it will be automatically drained to the outside of the water clock. Moreover, even if there is no direction in which water overflows, more water than the capacity of the water tank does not stay in the grid. In such a case, the amount of water that exceeds the capacity of the aquarium disappears with a mysterious force. Note that if the adjacent aquarium is placed on a platform that is even slightly higher than the original aquarium, water will not flow in that direction. For example, in the case of Fig. 3, 1/4 of the overflowing amount of water flows from the central tank to the left and right tanks and the back tank.

<image> | <image>
--- | ---
Figure 2 | Figure 3

Your job is to write a program that simulates this water clock.

Input

The input consists of multiple datasets. The number of data sets is 300 or less, and each has the following format.


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 and h are positive integers representing the number of columns and rows in the grid, respectively, and satisfy 1 ≤ w ≤ 10 and 1 ≤ h ≤ 10, respectively. fx, fy, fq represent the location (fx, fy) and flow rate (fq) of the grid where the water tank that flows water is placed. The unit of flow rate is cm ^ 3. These satisfy 0 ≤ fx <w, 0 ≤ fy <h, 1 ≤ fq ≤ 30000. The following h lines are each composed of w numbers separated by spaces, and represent the height of the table on which the aquarium is placed in the grid {i, j}. The unit is cm, which is an integer that satisfies 0 ≤ pi, j ≤ 1000. When pi, j = 0, there is no water tank in that place. The next line consists of a positive integer l that represents the number of measurements of the height of the water in the aquarium. This satisfies 1 ≤ l ≤ 10. The following l line contains three space-separated integer values, tk, xk, and yk. tk represents the measurement time, and xk and yk indicate the grid of the measurement location. It can be assumed that xk and yk always indicate a grid with an aquarium. It also satisfies 0 ≤ t ≤ 10000.

The end of the input is represented by a line containing two zeros.

Output

Output l integers for each dataset. The integer outputs the height of the water in the aquarium on the grid xk, yk at the specified time tk. The height of water after the decimal point is rounded down.

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
Four
5 2 0
10 2 1
100 2 2
250 2 3
0 0



Output for Sample Input


Five
Five
8
30
Five
13
Four






Example

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

5
5
8
30
5
13
4

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 10


struct LOC{
	LOC(){
		row = col = 0;
	}
	LOC(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	void set(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

struct Query{
	Query(int arg_T,int arg_x,int arg_y,int arg_query_index){
		T = arg_T;
		x = arg_x;
		y = arg_y;
		query_index = arg_query_index;
	}
	bool operator<(const struct Query &arg) const{

		return T < arg.T;
	}
	int T,x,y,query_index;
};

struct Edge{
	Edge(int arg_to,int arg_value){
		to = arg_to;
		value = arg_value;
	}
	int to,value;
};

struct Tank{
	int num_floor,num_over,HEIGHT;
};

struct Info{
	Info(){
		tank_index = 0;
		HEIGHT = 0;
	}
	Info(int arg_tank_index,int arg_HEIGHT){
		tank_index = arg_tank_index;
		HEIGHT = arg_HEIGHT;
	}
	bool operator<(const struct Info &arg) const{

		return HEIGHT < arg.HEIGHT; //高さの降順(PQ)
	}
	int tank_index,HEIGHT;
};

int W,H;
int diff_row[4] = {-1,0,0,1},diff_col[4] = {0,-1,1,0};
int P[SIZE][SIZE];
int INDEX[SIZE][SIZE];
int boss[SIZE*SIZE],height[SIZE*SIZE];
int num_adj[SIZE*SIZE];
double water[SIZE*SIZE];
double NUM = 30,ans[SIZE];
bool used[SIZE*SIZE];
vector<LOC> GROUP[SIZE*SIZE];
vector<Edge> G[SIZE*SIZE];
Tank tank[SIZE*SIZE];


bool rangeCheck(int row,int col){

	return row >= 0 && row <= H-1 && col >= 0 && col <= W-1;
}

int get_boss(int id){
	if(boss[id] == id)return id;
	else{
		return boss[id] = get_boss(boss[id]);
	}
}

int is_same(int x,int y){
	return get_boss(x) == get_boss(y);
}

void unite(int x,int y){
	int boss_x = get_boss(x);
	int boss_y = get_boss(y);

	if(boss_x == boss_y)return;

	if(height[boss_x] > height[boss_y]){

		boss[boss_y] = boss_x;

	}else if(height[boss_x] < height[boss_y]){

		boss[boss_x] = boss_y;

	}else{ //height[boss_x] == height[boss_y]

		boss[boss_y] = boss_x;
		height[x]++;
	}
}

void func(){

	for(int i = 0; i < W*H; i++){

		GROUP[i].clear();
		G[i].clear();
	}

	int index = 0;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			INDEX[row][col] = index++;
		}
	}

	int base_x,base_y,F;
	scanf("%d %d %d",&base_x,&base_y,&F);

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			scanf("%d",&P[row][col]);
		}
	}

	for(int i = 0; i < index; i++){

		boss[i] = i;
		height[i] = 0;
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			for(int i = 0; i < 4; i++){

				int adj_row = row+diff_row[i];
				int adj_col = col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				if(P[row][col] == P[adj_row][adj_col]){

					unite(INDEX[row][col],INDEX[adj_row][adj_col]);
				}
			}
		}
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){

			GROUP[get_boss(INDEX[row][col])].push_back(LOC(row,col));
		}
	}

	int num_out,total;

	//各連結水槽の、隣接水槽と隣接辺数を計算
	for(int i = 0; i < index; i++){
		if(GROUP[i].size() == 0)continue;

		num_out = 0;
		for(int k = 0; k < index; k++){

			num_adj[k] = 0;
		}

		for(int k = 0; k < GROUP[i].size(); k++){

			int base_row = GROUP[i][k].row;
			int base_col = GROUP[i][k].col;

			for(int a = 0; a < 4; a++){
				int adj_row = base_row+diff_row[a];
				int adj_col = base_col+diff_col[a];

				if(!rangeCheck(adj_row,adj_col)){ //範囲外は高さ0とみなす?

					num_out++;
					continue;
				}
				if(get_boss(INDEX[adj_row][adj_col]) == i ||
						P[base_row][base_col] < P[adj_row][adj_col])continue;

				num_adj[get_boss(INDEX[adj_row][adj_col])]++;
			}
		}

		total = 0;
		for(int k = 0; k < index; k++){
			if(num_adj[k] == 0)continue;

			G[i].push_back(Edge(k,num_adj[k]));
			total += num_adj[k];
		}

		tank[i].num_floor = GROUP[i].size();
		tank[i].num_over = total+num_out;

		tank[i].HEIGHT = P[GROUP[i][0].row][GROUP[i][0].col];
	}

	int num_query;
	scanf("%d",&num_query);

	vector<Query> V;

	int T,x,y;
	for(int i = 0; i < num_query; i++){

		scanf("%d %d %d",&T,&x,&y);
		V.push_back(Query(T,x,y,i));
	}

	sort(V.begin(),V.end());

	for(int i = 0; i < index; i++){

		water[i] = 0;
	}

	double add;
	int tmp_index;
	priority_queue<Info> Q;

	int pre = 0;

	for(int i = 0; i < V.size(); i++){

		add = (double)(V[i].T-pre)*(double)F;

		for(int k = 0; k < index; k++){
			used[k] = false;
		}

		tmp_index = get_boss(INDEX[base_y][base_x]); //流入水槽

		water[tmp_index] += add;
		Q.push(Info(tmp_index,tank[tmp_index].HEIGHT));

		while(!Q.empty()){

			Info info = Q.top();
			Q.pop();

			if(used[info.tank_index])continue;
			used[info.tank_index] = true;

			double OVER = water[info.tank_index]-NUM*NUM*NUM*tank[info.tank_index].num_floor;

			if(OVER <= 0)continue;

			water[info.tank_index] = NUM*NUM*NUM*tank[info.tank_index].num_floor;//満杯

			for(int k = 0; k < G[info.tank_index].size(); k++){

				water[G[info.tank_index][k].to] += (OVER*G[info.tank_index][k].value)/(double)tank[info.tank_index].num_over;

				Q.push(Info(G[info.tank_index][k].to,tank[G[info.tank_index][k].to].HEIGHT));
			}
		}

		tmp_index = get_boss(INDEX[V[i].y][V[i].x]);

		ans[V[i].query_index] = water[tmp_index]/(NUM*NUM*tank[tmp_index].num_floor);
		pre = V[i].T;
	}

	for(int i = 0; i < num_query; i++){

		printf("%.0f\n",floor(ans[i]));
	}
}

int main(){

	while(true){

		scanf("%d %d",&W,&H);
		if(W == 0 && H == 0)break;

		func();

	}

	return 0;
}