건강한 식단

어떤 대학의 캠퍼스는 $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$ 을 가지는 자판기의 수를 각각 이 순서대로 출력한다.