小鑫的新游戏

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小鑫很喜欢用矩阵来存储图,他觉得这样一目了然。今天他发明了一个新游戏,就是需要用到图的这种存储方式的。
首先,小鑫会有一个n*n的矩阵W,其中第i行第j列Wij代表着点i到点j的距离。
然后小鑫会按照某个序列将这n个点一一删去,每当某个点删去后,连向它的边也就不存在了。当他删掉这个点之前,他想知道还存在的这些点的最短路径之和是多少。
你能帮助他么?

Input

多组输入,到文件结束。
对于每一组而言。第一行有一个数n (1<n<500),代表点的个数。其次有n行每行n个数。第i行第j个数为Wij。1<Wij<100000,Wii=0.然后有一行n个数代表依次删掉的点的编号,点的编号是从1开始的。

Output

对于每组输入,输出有一行,有n个数,为题目的答案。

Sample Input

2
0 1
1 0
1 2

Sample Output

2 0

Hint

 

Source

lin