兔兔有一个有边权的有向图，包含n个点。这个图的每两个点之间都有两个方向的边。兔兔喜欢用他的图玩游戏，现在他发明了一种新游戏：

• 游戏包含n步。
• 第i步 兔兔从图中删掉编号为xi的点。当删除一个点时，这个点的出边和入边都会被删除。
• 在执行每一步之前，兔兔想知道所有点对间最短路长度的和。最短路可以经过任何没删掉的点。换句话说，如果我们假设d(i,v,u) 是在删掉xi前v和u间的最短路长度，那么兔兔想知道下面这个求和的值：∑_v,u,v≠ud(i,v,u)。

帮帮兔兔，输出每一步之前的和值。

第一行包含一个整数n(1≤n≤500) ，代表图中的顶点数。
下面n 行每行包含n个整数，代表边权：第i行的第j个数aij(1≤aij≤100000 ,aii=0)代表从i到j的边权。
最后一行包含n个整数：x1,x2,…,xn(1≤xi≤n) ，分别为兔兔每一步删掉的点的编号。

输出n个整数，第i个数等于游戏的第i步之前统计的和值。

1
0
1

0

样例2
输入：
2
0 5
4 0
1 2
输出：
9 0 


样例3
输入：
4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3
输出：
17 23 404 0