当前没有测试数据。

3.生物进化

题目描述

生物学家们发现了几种动物化石。他们将化石依次编号为$1$，$2$，$3$，$\ldots$，$n-1$，$n$。

经过简单的分析，他们发现了一些规律：若动物$A$是由动物$B$经过若干次进化而成的，则称$B$是$A$的祖先，特别地，任意一种动物都是它自己的祖先（经过$0$次进化）；若动物$A$是由动物$B$经过一次进化而成的，则称$B$是$A$的直系祖先；$1$号动物无直系祖先，其它每种动物都有且仅有一个直系祖先；发现的动物化石中，$1$号的是它们共同的祖先；所有的动物都是从低级向高级进化。

为了进一步确定生物进化的过程，生物学家们经过复杂的分析和计算，得出这些化石两两间的“差异程度”。“差异程度”有如下性质：对于两个物种$i$，$j$，它们的“差异程度”是一个非负整数，记为$D_{i,j}$；$D_{i,i}=0$，$i=j$时，$D_{i,j}=D_{j,i}=0$；若$i$是$k$的祖先，$k$是$j$的祖先则$D_{i,j}=D_{i,k}+D_{k,j}$；若$k$是$i$和$j$的所有公共祖先中最高级的，则$D_{i,j}=D_{i,k}+D_{k,j}$。因此，利用“差异程度”，就可以确定生物进化的过程。

但是化石数量实在太多了，于是，生物学家们希望能够帮助他们。

输入格式

第一行是一个整数$n$，表示化石种类数。

接下来$n$行，每行$n$个整数，第$i$行第$j$个是$D_{i,j}$，表示$i$和$j$的“差异程度”。

输出格式

$n-1$行，第$i$行是一个整数$c$，表示$i+1$号动物的直系祖先为$c$。

数据范围与提示

对于$100\%$的数据：$1 < n < 100$，$0 \leq D_{i,j} \leq 100000$。

样例

4
0 1 4 7
1 0 5 8
4 5 0 3
7 8 3 0

1
1
3