下沉的陆地

题目描述

有一座被海包围的 $H \times W$ 大小的岛屿。

岛屿被划分为 $H$ 行 $W$ 列的 $1 \times 1$ 区域,位于从上数第 $i$ 行、从左数第 $j$ 列的区域的海拔(相对于当前海平面)为 $A_{i,j}$。

从现在开始,海平面每年上升 $1$。

这里,与海或已沉入海中的区域上下左右相邻、且海拔不高于海平面的区域会沉入海中。

当某个区域新沉入海中时,与其上下左右相邻、且海拔不高于海平面的区域也会同时沉入海中,这一过程会针对新沉入的区域继续重复。

对每个 $i=1,2,\ldots, Y$,求从现在起 $i$ 年后仍位于海平面以上的岛屿面积。

输入格式

输入按以下格式从标准输入给出:

$H$ $W$ $Y$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$

输出格式

输出 $Y$ 行。 第 $i$ 行 $(1 \leq i \leq Y)$ 应包含从现在起 $i$ 年后仍位于海平面以上的岛屿面积。

样例

3 3 5
10 2 10
3 1 4
10 5 10

9
7
6
5
4

设 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的区域。接下来发生如下情况:

1 年后,海平面比现在高 $1$,但没有海拔为 $1$ 且与海相邻的区域,所以没有区域沉没。因此,第 1 行应输出 $9$。

2 年后,海平面比现在高 $2$,$(1,2)$ 沉入海中。这使得 $(2,2)$ 与已沉没区域相邻,且其海拔不大于 $2$,所以它也沉没。此时没有其他区域沉没。因此,共有两个区域沉没,第 2 行应输出 $9-2=7$。

3 年后,海平面比现在高 $3$,$(2,1)$ 沉入海中。没有其他区域沉没。因此,第 3 行应输出 $6$。

4 年后,海平面比现在高 $4$,$(2,3)$ 沉入海中。没有其他区域沉没。因此,第 4 行应输出 $5$。

5 年后,海平面比现在高 $5$,$(3,2)$ 沉入海中。没有其他区域沉没。因此,第 5 行应输出 $4$。

因此,按顺序各输出一行 $9$、$7$、$6$、$5$、$4$。

3 5 3
2 2 3 3 3
2 1 2 1 3
2 2 3 3 3

15
7
0

数据范围

• $1 \leq H, W \leq 1000$
• $1 \leq Y \leq 10^5$
• $1 \leq A_{i,j} \leq 10^5$
• 所有输入值都是整数。