题目描述

题目译自 Open Olympiad in Informatics 2021 Day2 T3 「Плитка для ванной」。

科斯塔有很多事情要做——装修正在如火如荼地进行！他需要贴墙纸、组装家具，还要不断清理垃圾。

今天，科斯塔想为浴室购买瓷砖。他来到一家商店，面对一个巨大的正方形展示墙。展示墙是一个 $n \times n$ 的网格，每个网格单元是一个颜色为 $c_{i,j}$ 的小瓷砖片。商店以包裹的形式出售瓷砖片——具体来说，只能购买展示墙的一个子正方形区域。

子正方形是指展示墙上的任意正方形区域，即任意集合 $S(i_0, j_0, k) = \{c_{i,j} \ | \ i_0 \leq i < i_0 + k, j_0 \leq j < j_0 + k\}$，其中 $1 \leq i_0, j_0 \leq n - k + 1$。

科斯塔尚未确定要购买多少瓷砖片，因此他考虑了所有可能大小的子正方形。同时，他明确不希望浴室里的瓷砖颜色过于杂乱，这使他能够缩小选择范围。请帮助科斯塔，对于每个 $k \leq n$，计算大小为 $k \times k$ 的子正方形中，包含不超过 $q$ 种不同颜色的数量。子正方形被视为不同，如果它们在展示墙上的位置不同。

输入格式

第一行包含两个正整数 $n$ 和 $q$ $(1 \leq n \leq 1500, 1 \leq q \leq 10)$，分别表示展示墙的尺寸和包裹中不同颜色的限制数量。

接下来的 $n$ 行，每行包含 $n$ 个正整数 $c_{i,j}$ $(1 \leq c_{i,j} \leq n^{2})$，其中第 $i$ 行的第 $j$ 个数字表示网格单元 $(i,j)$ 中瓷砖的颜色。

输出格式

对于每个 $k$ 从 $1$ 到 $n$，在单独的一行中输出一个整数，表示对科斯塔有吸引力的 $k \times k$ 大小的子正方形数量。

3 4
1 2 3
4 5 6
7 8 9

9
4
0

4 8
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7

16
9
4
0

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。