有一群朋友，一共有 $n$ 个人，他们都生活在不同的城市。他们生活在一个非对称世界里面，也就是说 $a$ 到 $b$ 的距离不一定等于 $b$ 到 $a$ 的距离。

有一天，他们的世界变回了对称世界，这个时候，任意两个人 $a,b$ 之间的距离变成了 $a$ 到 $b$ 的距离和 $b$ 到 $a$ 的距离中的最大值。

输入格式

输入第一行一个整数 $n(1≤n≤100)$ 表示图的点数。

接下里 $n$ 行，每行输入 $n$ 的整数，表示这个图的邻接矩阵，相邻两数之间以一个空格分隔。

保证对角线上的数字都为 $0$。

输出格式

输出一共 $n$ 行，每行 $n$ 个整数，表示回到对称世界以后的邻接矩阵，相邻两数之间以一个空格分隔。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 dist.in，输出文件为 dist.out

样例输入

3
0 6 0
1 0 1
9 1 0

样例输出

0 6 9
6 0 1
9 1 0