5 - Floodfill

The engineers are now trying to figure out how Atlantis sank based on some information they found in the buildings. What they discovered was amazing. Apparently the Atlantean scientists knew that there was going to be a problem. They collected ample data on rainfall and divided the entire continent into a grid of square cells in an effort to figure out which areas were going to flood and how badly. Each cell can hold a certain amount of water(in helenometers) before there is standing water.

You have found their simulations including the grid of cells with varying water retention capacity and rainfall events. During each rainfall event it rains X number of helenometers on some cell on the grid. All Saturated cells which are adjacent(Defined as all 8 cells surrounding the cell) are considered one large cell for the purpose of distributing water. When a cell fills up, the water is distributed equally to all adjacent unsaturated cells. If any of those cells fill up the water is distributed equally among the unsaturated cells adjacent to the one large cell it is now part of( i.e. the cells adjacent to the cell which overlowed into it and the cells adjacent to the cell which just filled up).

The simulation will run for several days and you will then output the water saturation levels of each cell at the end of the period. One thing to note is that you -must- flood all the adjacent cells around the flooded cell at the same time. The other thing that you need to be aware of is that the data found for each day is in order of the time that the rain fell so you will need to process each cell data completely before moving on to the next one as it apparently never rained in more than one place at once on Atlantis. All cells are devoid of water at the beginning of each case. After processing all the data for each case you will need to decide whether or not Atlantis sank based on that data. If all cells are filled and the water has nowhere to flood to, output "Atlantis Sank". However, if there was ample space for the water to flood to output the amount of water in each cell of the grid. If a cell on the edge of the grid fills up, then the ocean spaces are ignored, as all of Atlantis is surrouned by a giant levee not built by the US Corp of Engineers, so don't expect them to burst.

The grid is indexed starting from 0,0 being the top left square. Cells are calcluated from left to right and up to down. All overflow calculations should round to the nearest 1/100th.

Sample Input form:

Number of Cases (1 ≤ x ≤ 100) row length of grid (1 ≤ x ≤ 10) column length of grid(1 ≤ x ≤ 10) Water retention values for each cell of the grid(0 < x < < 10^7) number of days in simulation data for each day in the form of (Row Column Amount of rain)

Sample Input:

2
4
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
2
0 0 16
2 2 16
1 1 16
3 3 16
4
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1
0 0 4
3 3 4

Sample Output: