题目描述

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

某大学的学生园区是一个 $n \times n$ 的正方形网格，每个格子内都有一座建筑。相邻格子（即有公共边的格子）内的建筑通过通道相连。左上角的格子是学生宿舍，右下角的格子是教学楼。

园区内每座建筑（包括学生宿舍和教学楼）都有一台自动售货机，每台售货机只出售一种产品，例如只卖咖啡或只卖肉馅饼。学生每天从宿舍走到教学楼，选择一条最短路径通过通道前往。

大学管理层关注学生在沿途购买食物时的饮食多样性。对于每台售货机 $A_{i,j}$，计划找到一条从宿舍到教学楼的最短路径，该路径经过这台售货机，并且包含尽可能多出售与 $A_{i,j}$ 相同产品的售货机。这条路径上出售相同产品的售货机数量称为售货机 $A_{i,j}$ 的冗余度。其中，售货机 $A_{1,1}$ 位于宿舍，售货机 $A_{n,n}$ 位于教学楼。

你需要编写一个程序，根据售货机出售的产品信息，计算出从 $1$ 到 $2n-1$ 的每个冗余度值对应的售货机数量。

输入格式

输入文件的第一行包含一个整数 $n$ $(2 \leq n \leq 1500)$。

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

输出格式

输出文件应包含 $2n-1$ 个整数，分别表示冗余度为 $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$ 分，总分为 $100$ 分。测试点的评分是独立的，具体限制条件如下表所示：