说明

你有一张世界地图，表示为一个 $n \times m$ 的矩形。地图上的每个单元格属于 $k$ 个国家之一。每个国家所拥有的单元格集合是四连通的——这意味着，从该国家的任何一个单元格出发，你可以通过向下、向上、向左、向右移动，且不进入其他国家的领土，到达该国家的任何其他单元格。

在这动荡的时代，许多国家相互提出了领土要求。国家 $i$ 认为，包含其所有单元格的、边与地图边缘平行的最小矩形内的所有单元格，都是其历史领土。因此，国家 $i$ 对国家 $j$（$j \neq i$）提出领土要求，当且仅当国家 $j$ 有单元格位于国家 $i$ 的这个最小矩形内。

作为一名专业分析师，你的任务是对于每个国家 $i$，确定它向多少个其他国家提出了领土要求。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 2 \cdot 10^5$，$1 \le k \le nm \le 2 \cdot 10^6$）—— 分别表示地图的高度、地图的宽度以及不同国家的数量。

接下来的 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行包含 $a_{i1}, a_{i2}, \dots, a_{im}$（$1 \le a_{ij} \le k$）—— 分别表示单元格 $(i,1), (i,2), \dots, (i,m)$ 所属的国家编号。

保证每个国家 $k$ 至少拥有一个单元格。

保证每个国家的单元格集合是四连通的。

输出格式

输出 $k$ 个整数，其中第 $i$ 个整数表示国家 $i$ 提出领土要求的国家数量。

3 4 4
1 3 3 2
1 2 2 2
1 1 1 4

2 1 0 0

提示

翻译由 DeepSeek 完成