Islands

Time limit3sMemory limit512 MB

Summary

For several nondecreasing sea levels, count the connected regions of cells whose height is above the water level.

Level: Medium7 of 10
Topics: Union-find, Sorting, Graph, Implementation
Solved: No attempts yet

Problem

Deep in the Caribbean lies a rectangular island divided into an $n \times m$ grid. Every grid cell has a fixed height measured in meters.

The sea level keeps rising: in year $i$ the sea level is exactly $i$ meters. The island is made of sponge, so water flows freely through it — a cell is flooded whenever its height is at most the current sea level. Cells that are not flooded and share a common edge belong to the same unflooded area (a connected region).

For each of several years, determine how many separate unflooded areas the island has.

The picture below shows a $4 \times 5$ island; the numbers are the cell heights in meters and the unflooded cells are drawn darker. There are two unflooded areas in year 1 and three unflooded areas in year 2.

Year 1	Year 2

Input

The first line contains a positive integer $Z$ ( $Z \le 20$ ), the number of test cases. Each test case is given as follows.

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 1000$ ), the dimensions of the island. The next $n$ lines each contain $m$ integers in the range $[1, 10^9]$ , the heights of the cells. The next line contains an integer $T$ ( $1 \le T \le 10^5$ ). The last line contains $T$ integers $t_1, t_2, \ldots, t_T$ with $0 \le t_1 \le t_2 \le \cdots \le t_T \le 10^9$ , the sea levels (years) to query.

Output

For each test case, print a single line with $T$ integers $r_1, r_2, \ldots, r_T$ separated by single spaces, where $r_j$ is the number of unflooded areas when the sea level is $t_j$ .

Examples5

Example 1

Input

Expected output

2 3 1 0 0

Example 2
Input
```
1
1 1
5
3
0 5 10
```
Expected output
```
1 0 0
```
Example 3
Input
```
1
2 3
4 4 4
4 4 4
2
3 4
```
Expected output
```
1 0
```
Example 4
Input
```
1
3 3
2 1 2
1 1 1
2 1 2
3
0 1 2
```
Expected output
```
1 4 0
```

Example 5

Input

1
1 5
1 2 3 4 5
6
0 1 2 3 4 5

Expected output

1 1 1 1 1 0