D. Плитка для ванной
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кости очень много дел: ремонт в самом разгаре! Надо клеить обои, собирать мебель и постоянно вывозить мусор.

Сегодня Костя хочет купить плитку для ванной. Он пришел в магазин и оказался перед большим квадратным стендом с плиткой. Стенд представляет из себя квадрат из $$$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$$$.

Костя еще не знает, сколько кусочков плитки он хочет купить, и, соответственно, рассматривает подквадраты всех возможных размеров. При этом он точно не хочет слишком разноцветную плитку в ванной, что позволяет ему сузить выбор. Помогите Косте для каждого $$$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$$$): $$$j$$$-е число в $$$i$$$-й строке соответствует цвету плитки в клетке $$$(i,\,j)$$$.

Выходные данные

Для каждого $$$k$$$ от $$$1$$$ до $$$n$$$ выведите в отдельной строке по одному целому числу — количество подквадратов размера $$$k \times k$$$, в которых не более $$$q$$$ различных цветов.

Примеры
Входные данные
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
Примечание

В первом примере все цвета квадратиков плитки различные. Поскольку Костя не хочет, чтобы в купленном квадрате было больше $$$4$$$ цветов, он может купить себе любой подквадрат размера $$$1 \times 1$$$ или $$$2 \times 2$$$, но при этом не сможет купить квадрат размера $$$3 \times 3$$$.

Во втором примере есть повторяющиеся цвета. А именно, за счет ограничения $$$q = 8$$$ Костя может купить любой подквадрат $$$1 \times 1$$$ и $$$2 \times 2$$$, а также любой подквадрат $$$3 \times 3$$$, ведь в каждом таком подквадрате всего $$$7$$$ цветов. Весь стенд размера $$$4 \times 4$$$ Костя купить не сможет, потому что там будет $$$9$$$ цветов.