In recent years, because of the rapid expanding of institutes, the weather has become warmer and warmer. It directly leads to the rising of the level of the sea. Fortunately, peoples on Continent Catan have developed sufficient boating technology to adapt the rising sea level. They only want to know how many islands will form in the next few years, so they can prepare enough boats to maintain their cultures.
The map of Continent Catan can be expressed as grids, filled with the altitude of each grid. If the sea level is higher or equal to the altitude then the grid is sea, otherwise the grid is land. Two grids are considered connected if they are adjacent to each other. If some lands are connected then they are considered as an island. The sea level is increasing slowly as the years goes by, so it will be 0 in year 0, and it will be 1 in year 1, etc.
You were assigned the job to count the number of islands in each selected years. If you do it not well, your boss might FIRE you!
There is a number 1 <= T <= 10 at the beginning of input file, indicating the number of test cases. At the beginning of test cases, there will be 0<H<=1000 and 0<W<=1000 indicates the height and the width of the map of Continent Catan. Following H lines contains the map, each line has W numbers 0 <= aij <= 1000000 meaning the altitude of that grid.
After the map there is a number 1<= Q<=1000000, specifying the number of questions. Following Q numbers 0<= qi<=1000000 are the questioned years.
For each questioned year, calculate how many islands will be in this year, and print it as an integer in a line.
1 3 3 1 2 3 3 2 1 1 2 3 3 0 1 2
1 1 3
Migrated from old NTUJ.
pP
| No. | Testdata Range | Score |
|---|