题目描述

终于，卡卡西来到了一个叫"比特兰"的国家。"比特兰"是个很发达的国家，有着非常高科技的列车，和非常复杂的列车线路。具体来说：

• 从理论上，我们可以假设这个国家的高科技列车可以不消耗时间地从$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 \leq 10$
• 对于40%的数据，$n \leq 20$
• 对于60%的数据，$n \leq 50$
• 对于100%的数据，$n \leq 500$，$t_{ij} \leq 10^9$