Gilbert는 Ginkgo 회사의 네트워크 관리자이다. 그의 상사는 바닥의 어지러운 네트워크 케이블 때문에 화가 났다. 마침내 상사는 Gilbert에게 와서 이 게으른 관리자에게 컴퓨터와 스위치가 어떻게 연결되어 있는지 그림으로 보여 달라고 했다. 프로그래머인 Gilbert는 사무실을 돌아다니며 케이블과 스위치를 직접 살펴보기를 매우 꺼린다. 대신 그는 내내 컴퓨터 앞에 앉아서 측정과 약간의 수학적 사고로 이 일을 끝내기로 했다. 여러분의 임무는 측정값으로부터 네트워크 구조를 재구성하는 프로그램을 작성하여 그를 돕는 것이다.

컴퓨터의 수는 알려져 있고 스위치의 수는 알려져 있지 않다. 각 컴퓨터는 케이블로 스위치 하나에만 연결되고 다른 어떤 것에도 연결되지 않는다. 구체적으로 컴퓨터끼리 직접 연결되지 않으며, 한 컴퓨터가 두 개 이상의 스위치에 연결되지도 않는다. 스위치들은 케이블로 연결되어 트리(사이클이 없는 연결된 무방향 그래프)를 이룬다. 쓸모없는 스위치는 없다. 즉, 각 스위치는 적어도 한 쌍의 컴퓨터 사이의 경로 위에 있다.

종합하면 컴퓨터와 스위치는 함께 트리를 이루며, 컴퓨터는 리프이고 스위치는 내부 정점이다(그림 9 참조).

Gilbert는 모든 컴퓨터 쌍 사이의 거리를 측정한다. 두 컴퓨터 사이의 거리는 둘 사이 경로 위의 스위치 수에 1을 더한 값이다. 동등하게, 둘을 연결하는 데 쓰이는 케이블 수이다. 측정만으로 Gilbert가 실제로 이 거리를 어떻게 구하는지 궁금할 수 있다. 그는 자신이 발명한 매우 정교한 통계 처리 기법으로 이를 할 수 있다. 자세한 내용은 묻지 말자.

따라서 트리의 리프 사이 거리를 나타내는 행렬이 주어진다. 여러분의 임무는 이 행렬로 트리를 구성하는 것이다.

입력

입력은 거리 행렬의 열이며, 마지막에 0 하나만 있는 줄이 온다. 각 거리 행렬은 다음 형식이다.

$$N$$

$$\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1N}\\a_{21}&a_{22}&\cdots&a_{2N}\\\vdots&\vdots&\ddots&\vdots\\a_{N1}&a_{N2}&\cdots&a_{NN}\end{pmatrix}$$

그림 9: 컴퓨터와 스위치

$N$은 행렬의 크기, 즉 행의 수와 열의 수이다. $a_{ij}$는 $i$번째 리프 정점(컴퓨터)과 $j$번째 리프 사이의 거리이다. $2 \le N \le 50$이고 행렬이 대칭이며 대각 원소는 모두 0이라고 가정해도 된다. 즉, 모든 $i,j$에 대해 $a_{ii}=0$, $a_{ij}=a_{ji}$이다. 모든 비대각 원소 $a_{ij}$ ($i\ne j$)는 $2 \le a_{ij} \le 30$을 만족한다. 항상 해가 존재한다고 가정해도 된다. 즉, 주어진 리프 사이 거리를 갖는 트리가 존재한다.

출력

각 거리 행렬에 대해 주어진 리프 사이 거리를 갖는 트리를 찾아라. 그런 다음 각 내부 정점의 차수(즉, 각 스위치에 접한 케이블 수)를 오름차순으로 한 줄에 출력하라. 한 줄의 숫자는 공백 하나로 구분해야 한다. 줄에는 끝의 공백을 포함해 다른 어떤 문자도 있어서는 안 된다.

예제

입력 1

4
    0   2   2   2
    2   0   2   2
    2   2   0   2
    2   2   2   0
4
    0   2   4   4
    2   0   4   4
    4   4   0   2
    4   4   2   0
2
     0 12
    12 0
0

출력 1

4
2 3 3
2 2 2 2 2 2 2 2 2 2 2