题目描述

有一个包含 $n$ 个节点的有向完全图，图中节点编号从 $1$ 到 $n$。初始时任意两点间都存在着两条反向的有向边。接下来你需要对这个有向图进行 $n$ 步操作：

• 第 $i$ 步操作，你需要从图中删除编号为 $x_i$ 的点；与此同时，图中所有与 $x_i$ 点相连的边也将会被删除。
• 在每一步删除节点前，你需要统计图中所有目前还存在的点之间的最短路径长度之和。换句话说，如果我们定义 $d(i, v, u)$ 表示第 $i$ 步操作（即删除 $x_i$ 节点）之前从 $v$ 到 $u$ 的最短路径长度，则你需要求解的是 $\sum\limits_{v,u,v \neq u} d(i, v, u)$ 。

请计算每一步（删除 $x_i$ 之前）对应的最短路径长度之和。

输入格式

输入的第一行包含一个整数 $n(1 \le n \le 500)$，表示图中节点个数。

接下来 $n$ 行，每行包含 $n$ 个整数，其中第 $i$ 的第 $j$ 个整数表示从节点 $i$ 连向节点 $j$ 的有向边的长度 $a_{i,j}(1 \le a_{i,j} \le 10^5, a_{i,i} = 0)$。

接下来一行包含 $n$ 个各不相同的整数 $x_1, x_2, \ldots x_n(1 \le x_i \le n)$，两两之间以一个空格分隔，分别表示每一步要删除的点。

输出格式

输出共一行，包含 $n$ 个整数，两两之间以一个空格分隔，其中第 $i$ 个整数表示第 $i$ 步操作（删除 $x_i$ 节点）之前图中所有节点的最短路径长度之和。

样例

1
0
1

0

2
0 5
4 0
1 2

9 0 

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 

数据范围

• 对于 $20\%$ 的数据，$n \le 10, a_{i,j} \le 10$；
• 对于 $50\%$ 的数据，$n \le 100$；
• 对于 $100\%$ 的数据，$1 \le n \le 500, 1 \le a_{i,j} \le 10^5$。