给你一个大小为 $n \times m$ 的矩形世界地图。地图上的每个格子都属于 $k$ 个国家之一。每个国家的格子集合都是边相邻连通的——这意味着从该国家的任意一个格子出发，你都可以在不进入其他国家领土的情况下，通过向下、向上、向左和向右移动到达该国家的任意其他格子。

在这些动荡的时期，许多国家之间存在领土争端。国家 $i$ 将包含其所有格子的、边平行于地图边缘的最小矩形区域（即包围盒）视为其历史领土。因此，国家 $i$ 对所有在国家 $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$ 提出领土要求的国家数量。

样例

输入样例 1

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

输出样例 1

2 1 0 0