题目背景

译自 ROI 2014 Day2 T3. Здоровое питание

题目描述

某大学的学生城规划为一个 $n \times n$ 的正方形网格，每个格子里都有一栋建筑。如果两栋建筑位于有公共边的相邻格子中，它们之间就有一条连通的通道。在正方形的左上角是学生宿舍，在右下角是教学楼。每栋建筑中（包括宿舍与教学楼）都设有一台自动售货机，每台售货机只出售一种食品，例如：仅售咖啡，或仅售肉馅饼等。学生每天都会从宿舍出发，沿着通道前往教学楼，并选择一条最短路径。

校方希望研究学生在行进过程中购买食品的多样性。对于每一台售货机 $A_{i,j}$，希望找到一条经过该售货机的最短路径，并且该路径上与 $A_{i,j}$ 出售相同食品的售货机数量尽可能多。该数量称为售货机 $A_{i,j}$ 的冗余度。已知售货机 $A_{1,1}$ 位于宿舍内，而 $A_{n,n}$ 位于教学楼内。

请编写程序，根据各售货机所售食品的信息，统计冗余度为 $1, 2, \ldots, 2n - 1$ 的售货机各有多少台。

输入格式

第一行包含一个整数 $n$（$2 \leqslant n \leqslant 1500$）。

接下来的 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行第 $j$ 个数表示售货机 $A_{i,j}$ 所售食品的编号。食品编号的取值范围为 $1$ 到 $n^2$。

输出格式

输出共 $(2n - 1)$ 个整数，第 $k$ 个数表示冗余度等于 $k$ 的售货机数量（$k = 1, 2, \ldots, 2n - 1$）。

3
1 1 1
2 2 2
3 3 3

0
0
9
0
0

5
1 4 1 3 5
2 1 4 1 2
5 1 1 4 5
3 5 1 1 2
4 3 5 1 1

2
4
9
0
0 
1
1
8
0

提示

本题共 50 个测试，每个测试独立计分，每个测试 2 分。测试中使用的 $n$ 值如下表所示：