Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
3-dimensional Musical Water-fence
Time Limit: 8000MSMemory Limit: 65536K
Total Submissions: 164Accepted: 50
Case Time Limit: 4000MS

Description

Once Farmer John was washing his dirty clothes. Staring at lots of buckets, he was inspired suddenly. He said, "I can make a 3-dimensional musical water-fence (abbr. 3dmwf) like this."

After ages Farmer John shaped a piece of wood into a perfect 3dmwf. As figure A illustrates, the 3dmwf is an array of n rows and m columns of squares. And each square in the ith row and jth column is entirely occupied by a block, bij of height hij. And there is a tap over each block which can pour water.

Figure A: A 3-dimensional musical water-fence

heights of the blocks are

512118
152414
16137
131096

If Farmer John turns on a tap some water will be poured onto the block under that tap due to the gravity. As soon as the water crashes onto the block a dulcet sound will be made. And the tune of the sound is determined by the height of the block that makes the sound. Farmer John dislikes the same tune made by two different blocks. So no blocks has the same height. For simplicity we assume that the height of each block is between 1 and n × m.

We define pour(i,j,k) as the operation pouring k units of water onto the block bij. It is apparent that after pouring water onto 3dmwf probably some water will remain in concave holes.

When we pour(i,j,k) one and only one of the following two cases occurs:

(1) There is no water on the bij and there is some neighboring block whose horizontal line is lower than the bij.

Let Sum be the number of those neighboring blocks. Then pour(i,j,k) is equivalent to pour(i',j',kSum) where bi'j' is one of those neighboring blocks. That means the water will flow to all the lower neighboring blocks equally.

For example, in the previous figure,

pour(4,1,27)<=>
pour(4,0,9), pour(5,1,9), pour(4,2,9) <=>
waste 18 units of water, pour(5,2,3) , pour(4,3,3), pour(3,2,3) <=>
waste 21 units of water, pour(5,3,1), pour(4,4,1), pour(3,3,1), pour(3,2,3) <=>
waste 22 units of water, pour(5,4,0.5), pour(4,5,0.5), pour(3,3,1), pour(3,2,3) <=>
waste 23 units of water, pour(3,3,1), pour(3,2,3).
Obviously the water of pour(3,3,1) and pour(3,2,3) will be trapped in the concave hole formed by b22,b23,b32 and b33. So finally the volume of the waste water is 23 units.

(2) There is some water on the bij or there is no neighboring block whose horizontal line is lower than bij.
The k units of water will be mixed together with the water already on the bij. Then the horizontal line of those mixed the water will rise up until impossible because there is an exit that makes the water out of the concave hole.
For example, in the previous figure, continuing analyzing the last example,
(A)pour(3,2,3). After pouring 1 unit of water the horizontal lines of all blocks will become

 
512118
152414
16237
131096

And then after pouring 2 units of water the chart above will be become

512118
153414
16337
131096

(B)pour(3,3,1). After pouring 1 unit of water the chart above will become

512118
15313414
163133137
131096

(C)If we go on pouring a lot of water onto the concave hole, the chart above will become

512118
157714
16777
131096

The redundant water will flow away through the b34.

On a sunny day, after farming on his vast farm, Farmer John was exhausted. He wanted to listen to some dulcet music. So he composed a long music score for the 3dmwf. The music score is a list of pour(i,j,k) arranged in specific order. And now he invited his friends, Wang Dong, Guo Huayang, Chen Danqi, He Yijun to help him operate 3dmwf.

You know, Farmer John is an abstemious farmer. He doesn't want to waste too much water for playing music on 3dmwf. Could you tell him the volume of the total waste water?

Input

The input begins with two numbers, n and m, indicating the length of the row and the column respectively.
The next n lines each contain m integers indicating the height of wood blocks.
The next line contains a single integer, t, the size of the music score.
The next t lines each contain three integers, i,j, and k, indicating pour(i,j,k). The order of pour(i,j,k) in the input is the same as that in the music score.

Output

Print the volume of total waste water with 2 digits after the decimal point.

Sample Input

Sample Input 1
4 4
5 12 11 8
15 2 4 14
16 1 3 7
13 10 9 6
1
4 1 27

Sample Input 2
4 4
5 12 11 8
15 2 4 14
16 1 3 7
13 10 9 6
2
4 1 27
2 2 100

Sample Output

Sample Output 1
23.00

Sample Output 2
109.00

Hint

1≤n≤1000
1≤m≤1000
0≤t≤1000000
0≤k≤1000000

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator