Shortest Route Accumulation

Một mạng lưới máy chủ gồm $n$ nút được đánh số từ $1$ đến $n$. Giữa hai nút phân biệt bất kỳ luôn có đường truyền theo cả hai chiều.

Người quản trị hệ thống tiến hành quy trình bảo trì gồm $n$ bước. Tại bước thứ $i$, nút $x_i$ bị ngắt khỏi mạng lưới, kéo theo tất cả các đường truyền nối với nút $x_i$ cũng bị xóa bỏ.

Trước khi thực hiện mỗi bước bảo trì, quản trị viên cần tính tổng độ trễ ngắn nhất giữa tất cả các cặp nút còn hoạt động trong mạng lưới. Đường đi ngắn nhất giữa hai nút có thể đi qua bất kỳ nút nào hiện còn hoạt động.

Hãy tính và in ra tổng độ trễ ngắn nhất giữa mọi cặp nút còn lại ngay trước mỗi bước bảo trì.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ ($1 ≤ n ≤ 500$) là số lượng nút trong mạng lưới.

Tiếp theo là $n$ dòng, mỗi dòng chứa $n$ số nguyên. Số thứ $j$ trên dòng thứ $i$ là $a_{ij}$ ($1 ≤ a_{ij} ≤ 10^5$, $a_{ii} = 0$) đại diện cho độ trễ truyền tải trực tiếp từ nút $i$ đến nút $j$.

Dòng cuối cùng chứa $n$ số nguyên phân biệt $x_1, x_2, ..., x_n$ ($1 ≤ x_i ≤ n$) là thứ tự các nút lần lượt bị ngắt khỏi mạng.

Kết quả

In ra $n$ số nguyên trên một dòng, số thứ $i$ là tổng độ trễ ngắn nhất giữa tất cả các cặp nút còn lại ngay trước bước bảo trì thứ $i$.

Chấm điểm

Subtask 1 (30 points). $n ≤ 80$

Subtask 2 (70 points). $1 ≤ n ≤ 500$

Ví dụ

Input

1
0
1

Output

0

Ghi chú

Kết quả của mỗi bước có thể vượt quá giới hạn của kiểu số nguyên 32 bit, do đó cần sử dụng kiểu dữ liệu số nguyên 64 bit để lưu trữ tổng.