P15308 [VKOSHP 2025] Big World Politics

You are given a map of the world, represented as a rectangle of size $n \times m$. Each cell of the map belongs to one of $k$ countries. The set of cells of each country is connected by sides---this means that from any cell, you can reach any other cell of the same country by moving down, up, left, and right, without entering the territory of another country. In these troubled times, many countries have territorial claims against each other. Country $i$ considers all cells lying within the minimum rectangle with sides parallel to the edges of the map that contains all cells belonging to the country as its historical territories. Thus, country $i$ has territorial claims against all countries $j$ that have cells within the minimum rectangle of country $i$, except for country $i$ itself. As a professional analyst, your task is to determine for each country $i$ how many countries it has territorial claims against.

The first line of input contains three integers $n$, $m$, and $k$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le k \le nm \le 2 \cdot 10^6$) --- the height of the map, the width of the map, and the number of different countries, respectively. The following $n$ lines contain $m$ integers each, where the $i$-th line contains $a_{i1}, a_{i2}, \dots, a_{im}$ ($1 \le a_{ij} \le k$) --- the numbers of the countries to which the cells $(i,1), (i,2), \dots, (i,m)$ belong, respectively. It is guaranteed that each of the $k$ countries has at least one cell. It is guaranteed that the set of cells of each country is connected by sides.

Output $k$ integers, where the $i$-th integer is the number of countries that country $i$ has territorial claims against.