下沉的陆地

题目描述

有一个面积为 $H \times W$ 的小岛，四面环海。 该岛被分成 $H$ 行和 $W$ 列的 $1×1$ 个部分，从顶部起 $i$ 行和从左侧起 $j$ 列的部分(相对于当前海平面)的海拔高度为 $A_{i,j}$。

从现在开始，海平面每年上升 $1$ 。 在这里，垂直或水平临海的地段或沉入海中的地段，其标高不大于海平面，就会沉入海中。 在这里，当一个断面新z沉入海中时，垂直或水平相邻的标高不大于海平面的断面也会同时沉入海中，新沉入海中的断面重复这一过程。

对于每个 $i=1,2, \dots,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$ 年后海平面以上的岛屿面积。

样例 #1

样例输入 #1

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

样例输出 #1

9
7
6
5
4

样例 #2

样例输入 #2

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

样例输出 #2

15
7
0

提示

数据范围

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

样例 $1$ 解释

让 $(i,j)$ 表示从上往下第 $i$ 行和从左往上第 $j$ 列的部分。然后，会发生以下情况：

• 在 $1$ 年之后，海平面比现在高出 $1$，但是没有海拔高度为 $1$ 的地段与海相邻，所以没有地段下沉。因此，第一行应包含 $9$。
• $2$ 年后，海平面比现在高出 $2$， $(1,2)$ 沉入海中。这使得 $(2,2)$ 与下沉地段相邻，其海拔高度不高于 $2$ ，所以也下沉了。此时没有其他地段下沉。因此，有两个部分下沉，第二行应包含 $9−2=7$。
• $3$ 年后，海平面比现在高出 $3$，$(2,1)$ 沉入海中。其他部分没有下沉。因此，第三行应包含 $6$。
• $4$ 年后，海平面比现在高出 $4$，$(2,3)$ 沉入大海。其他部分没有下沉。因此，第四行应包含 $5$。
• $5$ 年后，海平面比现在高出 $5$，$(3,2)$ 沉入大海。其他部分没有下沉。因此，第五行应包含 $4$ 。

因此，依次打印 $9$，$7$，$6$，$5$，$4$ ，每行打印一行。