markdown

B. Greg 与图

时间限制：每个测试点 $3$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

Greg 有一个带权有向图，包含 $n$ 个顶点。在这个图中，任意两个不同顶点之间都有双向的边。Greg 喜欢玩这个图，现在他发明了一个新游戏：

• 游戏共有 $n$ 步。
• 在第 $i$ 步，Greg 从图中删除编号为 $x_i$ 的顶点。删除一个顶点时，所有与该顶点相连的入边和出边也会被一并删除。
• 在执行每一步之前，Greg 想知道当前剩余顶点中所有顶点对之间最短路径长度之和。最短路径可以经过任意剩余顶点。换句话说，假设 $d(i, v, u)$ 表示在删除顶点 $x_i$ 之前形成的图中，顶点 $v$ 到顶点 $u$ 的最短路径长度，那么 Greg 想知道以下和式的值：

请帮助 Greg，在每一步之前输出所需的和值。

输入

第一行包含一个整数 $n$（$1 \le n \le 500$）—— 图中顶点的数量。

接下来的 $n$ 行每行包含 $n$ 个整数 —— 图的邻接矩阵：第 $i$ 行第 $j$ 个数 $a_{ij}$（$1 \le a_{ij} \le 10^5$，$a_{ii} = 0$）表示从顶点 $i$ 到顶点 $j$ 的边的权重。

最后一行包含 $n$ 个互不相同的整数：$x_1, x_2, \dots, x_n$（$1 \le x_i \le n$）—— Greg 依次删除的顶点编号。

输出

输出 $n$ 个整数 —— 第 $i$ 个数等于第 $i$ 步之前所需的和值。

注意：在 C++ 中，请勿使用 %lld 说明符来读写 64 位整数。建议使用 cin、cout 流或 %I64d 说明符。

样例

输入样例 1

1
0
1

输出样例 1

0

输入样例 2

2
0 5
4 0
1 2

输出样例 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

输出样例 3

17 23 404 0