CF1500D Tiles for Bathroom

Kostya 非常忙：他正在装修自己的房子！他需要贴墙纸、组装家具、扔掉垃圾。 今天，Kostya 正在为浴室购买瓷砖。他正站在商店里一个大型的正方形瓷砖展台前。展台是一个 $n \times n$ 的正方形网格，每个格子里有一块颜色为 $c_{i,\,j}$ 的小瓷砖。商店只以包装出售瓷砖：更具体地说，你只能购买原始正方形中的一个子正方形区域。 一个子正方形是展台上的任意一个正方形区域，即任意集合 $S(i_0, j_0, k) = \{c_{i,\,j}\ |\ i_0 \le i < i_0 + k,\, j_0 \le j < j_0 + k\}$，其中 $1 \le i_0, j_0 \le n - k + 1$。 Kostya 还不知道需要多少瓷砖，所以他考虑了所有可能大小的子正方形。他不希望浴室颜色太花哨。请帮助 Kostya 统计对于每个 $k \le n$，有多少个大小为 $k \times k$ 的子正方形区域中，瓷砖颜色种类不超过 $q$ 种。若两个子正方形在展台上的位置不同，则认为它们是不同的。

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 1500$，$1 \le q \le 10$），分别表示展台的大小和子正方形中颜色种类的最大限制。 接下来的 $n$ 行，每行包含 $n$ 个整数 $c_{i,\,j}$（$1 \le c_{i,\,j} \le n^2$）：第 $i$ 行第 $j$ 个整数表示格子 $(i,\,j)$ 的瓷砖颜色。

对于每个 $k$ 从 $1$ 到 $n$，输出一个整数，表示有多少个大小为 $k \times k$ 的子正方形区域中，瓷砖颜色种类不超过 $q$ 种。

在第一个样例中，所有颜色都不同。Kostya 不希望子正方形有超过 $4$ 种颜色，所以他可以购买任意 $1 \times 1$ 或 $2 \times 2$ 的子正方形，但不能购买 $3 \times 3$ 的子正方形。 在第二个样例中，有些颜色出现了多次。由于 $q = 8$，Kostya 可以购买任意 $1 \times 1$、$2 \times 2$ 和 $3 \times 3$ 的子正方形，因为这些子正方形中最多只有 $7$ 种不同颜色。他不能购买整个 $4 \times 4$ 的展台，因为其中有 $9$ 种颜色。 由 ChatGPT 4.1 翻译