Dr. Sheldon Cooper is working on a project that works on the 2D concept of the universe. In this project, he will have to tell how many gaseous regions were Discretely left out after the famous big bang occurred. To help him with the project, Dr. Amy Farah came with an idea. Here she will tell you some data points on the model grid where gases might have exploded in the first place. Just like the Gradient Vector Flow(GVF), Dr. Sheldon will trace the region of gases passing through a layer of clouds by the following process. Can you help him design the project?
They will have an N x M 2D image of the universe, where each of the coordinates a(i,j) will tell them the concentration of the layer of the clouds.
Next Dr. Amy will suggest P points p(x,y) on the universe model where there have been an explosion of gases. It is considered that the gases simultaneously will keep on passing to adjacent cloud (vertical and horizontal direction) if the difference of the cloud layer density is not more than the cross-over value D. The cross-over value of all the explosions are not same. Two explosions may have different cross-over values.
If anyhow two gaseous regions have some common coordinates or any adjacent cell (vertical and horizontal) has gas in it too, they will merge and create a single region.
(see sample input 2 and 3 for explanation).
Find the number of gaseous region in the universe.
Input
- The number of test cases T (1 ≤ T ≤ 20). Next T cases will have the following property.
- 2 integers: N and M. 3 ≤ N,M ≤ 50.
- Next N lines will have M integers each of which are the values of a(i,j).
1 ≤ i ≤ N , 1 ≤ j ≤ M , 1 ≤ a(i,j) ≤ 1000000 - Next line will contain an integer P ( 1 ≤ P ≤ N*M ), the number of points where the gas may have exploded.
- Next P lines will have 3 integers, x, y and D, the coordinates and the cross-over value for that point.
1 ≤ x ≤ N , 1 ≤ y ≤ M , 0 ≤ D ≤ 1000000
Output
For each case print the case number and the number of discrete gaseous regions.
Sample
| Input | Output |
|---|---|
3 4 5 6 1 3 20 5 15 18 5 2 2 5 7 10 3 4 12 2 7 5 1 2 3 1 2 2 4 1 4 4 10 11 18 1 8 100 18 20 1 7 13 1 10 20 25 6 2 3 1 6 1 3 5 3 5 1 1 1 1 5 6 1 1 9 4 2 3 4 5 1 2 3 5 3 3 3 1 | Case 1: 2 Case 2: 1 Case 3: 1 |
In the 2nd case, 2 region gets merged due to common coordinate.
In 3rd test case the explosion will happen at A(3,5) and B(3,3). From A the gas will spread out to (3,5)->(2,5) -> (1,5) because the difference is less than D. Similarly, from B the gas will spread out to (3,3)->(3,2)->(3,1) and (3,3)->(3,4). Though there is no common coordinate but they share a common edge where there is gas, e.i. the edge of (3,4) and (3,5). So they merge and form a single region.
