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

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

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

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

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

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

样例输入

3
0 6 0
1 0 1
9 1 0

样例输出

0 6 9
6 0 1
9 1 0