Greg has a weighed directed graph, consisting of *n* vertices. In this graph any pair of distinct vertices has an edge between them in both directions. Greg loves playing with the graph and now he has invented a new game:
 -  The game consists of *n* steps. -  On the *i*-th step Greg removes vertex number *x*<sub class="lower-index">*i*</sub> from the graph. As Greg removes a vertex, he also removes all the edges that go in and out of this vertex. -  Before executing each step, Greg wants to know the sum of lengths of the shortest paths between all pairs of the remaining vertices. The shortest path can go through any remaining vertex. In other words, if we assume that *d*(*i*, *v*, *u*) is the shortest path between vertices *v* and *u* in the graph that formed before deleting vertex *x*<sub class="lower-index">*i*</sub>, then Greg wants to know the value of the following sum: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/90b01d654bf6bf2750396d13f2082c090a85368a.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 
Help Greg, print the value of the required sum before each step.
The first line contains integer *n* (1 ≤ *n* ≤ 500) — the number of vertices in the graph.

Next *n* lines contain *n* integers each — the graph adjacency matrix: the *j*-th number in the *i*-th line *a*<sub class="lower-index">*ij*</sub> (1 ≤ *a*<sub class="lower-index">*ij*</sub> ≤ 10<sup class="upper-index">5</sup>, *a*<sub class="lower-index">*ii*</sub> = 0) represents the weight of the edge that goes from vertex *i* to vertex *j*.

The next line contains *n* distinct integers: *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> (1 ≤ *x*<sub class="lower-index">*i*</sub> ≤ *n*) — the vertices that Greg deletes.
# https://codeforces.com/problemset/problem/296/D
import copy

N = int(input())

# M = [[math.inf for _ in range(N)] for _ in range(N)]
M = []

# parse adjacency matrix
for n in range(N):
    j_w = list(map(int, input().split()))  # weights of edge going from vertex i to j
    M.append(j_w)  # does this handle no edges? whatever

rem = list(map(int, input().split()))


def floyd_marshall(m):
    for k in range(len(m)):
        for i in range(len(m)):
            for j in range(len(m)):
                newd = m[i][k] + m[k][j]
                if newd < m[i][j]:
                    m[i][j] = newd


def prune(m: [], d):
    for x in range(len(m)):
        m[x].pop(d)
    m.pop(d)


def sum2d(m):
    s = 0
    for i in m:
        s += sum(i)
    return s


m_pruned = M
for i, r in enumerate(rem):
    # print(m_pruned)
    m_pruned_copy = copy.deepcopy(m_pruned)
    floyd_marshall(m_pruned_copy)
    print(sum2d(m_pruned_copy), end=' ')
    # print('-', rem, r, i)
    prune(m_pruned, r-1)
    # print(m_pruned)

    for x in range(i + 1, len(rem)):
        if rem[x] > r:
            rem[x] = rem[x] - 1
