题目描述
生物学家们发现了几种动物化石。他们将化石依次编号为 $1,2,3,\cdots,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$ 行，第 $n$ 行是一个整数 ，表示 $n$ 号动物的直系祖先为 。
样例输入输出
输入#1
复制
4
0 1 4 7
1 0 5 8
4 5 0 3
7 8 3 0
提示
对于 $100\%$ 的数据，$1 \leq n \leq 1000, 0 \leq D_{i,j} \leq 100000$。