测试数据来自 system/1937

描述

这是一个太阳从西边升起的情人节，木姑娘邀请我一起去逛街。

城市中有n个路口，它们两两之间存在道路。

路口i到路口j之间的道路距离为Aij，保证了Aij=Aji且Aii=0。

紫色的阳光养育着人心罪恶的萌发，城市的道路被以一种随机的方式，形成了树的结构，很多道路没有了，只保留了n-1条道路，却仍然保证了城市的连通性。

但是，木姑娘要逛街，逛街要走最短路径，不是么？

格式

输入格式

第一行一个整数n。下面n行每行n个整数，第i行第j个整数为Aij。
数据保证Aii=0且Aij=Aji对于所有i,j成立。
2<=n<=1000。
-1000<=Aij<=1000。

输出格式

输出n行。每行包含n个实数。第i行第j个整数为i到j的路径的期望长度，答案四舍五入保留到小数点后第四位。
（也就是问，随机得到一棵生成树，然后在这棵树上i到j的距离的期望值是多少。）

样例1

样例输入1

3
0 1 1
1 0 1
1 1 0

样例输出1

0.0000 1.3333 1.3333
1.3333 0.0000 1.3333
1.3333 1.3333 0.0000

限制

对于60％的数据，n<=5。
对于100％的数据，n<=500。

来源

感谢**Sevenkplus**