题目描述

终于，卡卡西来到了一个叫“比特兰”的国家，“比特兰”是个很发达的国家, 有着非常高科技的列车，和非常复杂的列车线路。具体来说，从理论上，我们可以假设这个国家的高科技列车可以不消耗时间的从 $A$ 地瞬间转移到 $B$ 地。同时，铁路线路复杂到，每对城市之间都有列车连接。但是不幸的是，由于这种列车运行需要很多维护工作，所以每天只能发出一次。从 $i$ 到 $j$ 的列车($i \neq j$)会在 $t_{ij}$ 时间发出(保证 $t_{ij}$ 两两不同)。

如果有一条路径链接$A$和$B$两个城市，并且满足路径上的每一条边的发车时间单调递增(也就是说经过的每段铁路的发出时间都要大于上一段的,因为我们 需要从上一段铁路换乘下一段铁路)。 现在“比特兰”的铁路局想要知道，一天之内，对于每一对 $i$ 和 $j$，如果想要从 $i$ 到达 $j$，最早多早能到达呢?

输入格式

第1行是一个整数 $n$，接下来 $n$ 行，每行 $n$ 个数表示 $t_{ij}（i=j，t_{ij}=0）$。

输出格式

$n$行，每行 $n$ 个数表示 $i$ 到 $j$ 最早的到达时间。

样例

输入#1

3
0 4 5
2 0 3
1 6 0

输出#1

0 4 5
2 0 3
1 4 0

数据范围

对于 20%的数据,$n≤10$ 对于 40%的数据,$n≤20$ 对于 60%的数据,$n≤50$ 对于 100%的数据,$n≤500, t_{ij}≤10^9$