Water Clock

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)

--- 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.

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

inputFormat

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.

outputFormat

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

样例

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

</p>