У Кости очень много дел: ремонт в самом разгаре! Надо клеить обои, собирать мебель и постоянно вывозить мусор.
Сегодня Костя хочет купить плитку для ванной. Он пришел в магазин и оказался перед большим квадратным стендом с плиткой. Стенд представляет из себя квадрат из \(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\) различных цветов плитки. Подквадраты считаются различными, если их расположение на стенде не совпадает.
Выходные данные
Для каждого \(k\) от \(1\) до \(n\) выведите в отдельной строке по одному целому числу — количество подквадратов размера \(k \times k\), в которых не более \(q\) различных цветов.
Примечание
В первом примере все цвета квадратиков плитки различные. Поскольку Костя не хочет, чтобы в купленном квадрате было больше \(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\) цветов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 2 3
4 5 6
7 8 9
|
9
4
0
|
|
2
|
4 8
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
|
16
9
4
0
|