题目描述

给定一张有 $n$ 个结点的带权有向完全图。任意两个不同结点之间都各有一条有向边。

接下来会依次删除结点 $x_1,x_2,\dots,x_n$。在删除第 $i$ 个结点之前，图中仍保留 $x_i,x_{i+1},\dots,x_n$ 这些结点以及它们之间的边。

对于每一步，求当前图中所有有序结点对 $(u,v)$ 的最短路长度之和。最短路只能经过当前仍保留的结点。

输入格式

第一行输入一个整数 $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$），表示删除顺序。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示删除第 $i$ 个结点之前，当前图中所有有序结点对的最短路长度之和。

样例

样例 1

输入：

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