Здоровое питание

План студенческого городка некоторого университета представляет собой квадрат $n \times n$, в каждой клетке которого расположено здание. Здания соединены переходами, если они расположены в клетках, имеющих общую сторону. В левом верхнем углу квадрата расположено студенческое общежитие. В правом нижнем углу расположен учебный корпус.

В каждом из зданий, включая общежитие и учебный корпус, расположен автомат, торгующий ровно одним продуктом, например, только кофе или только пирожками с мясом. Студенты каждый день ходят из общежития в учебный корпус по переходам, выбирая один из кратчайших путей.

Руководство университета заинтересовалось разнообразием питания студентов, покупающих продукты в автоматах по ходу движения. Для каждого автомата $A\_{i,j}$ планируется найти кратчайший путь из общежития в учебный корпус, проходящий через этот автомат и содержащий как можно больше автоматов, торгующих тем же самым продуктом, что и автомат $A\_{i,j}$. Количество таких автоматов на этом пути называется избыточностью автомата $A\_{i,j}$. При этом автомат $A\_{1,1}$ находится в общежитии, а автомат $A\_{n,n}$ --- в учебном корпусе.

Требуется написать программу, которая по информации о продуктах, продаваемых автоматами, для каждого из чисел в диапазоне от $1$ до $2n - 1$ определяет число автоматов с таким значением избыточности.

Первая строка входного файла содержит целое число $n$ ($2 \leqslant n \leqslant 1500$). Следующие $n$ строк содержат по $n$ чисел в каждой. В $i$-й из этих строк $j$-е число соответствует номеру продукта, продающегося в автомате $A\_{i,j}$. Номера продуктов находятся в диапазоне от $1$ до $n^2$.

Выходной файл должен содержать $(2n-1)$ целых чисел --- количество автоматов с избыточностями $1, 2, \ldots, 2n - 1$ соответственно.