Xóa dần các đỉnh

Cho đồ thị có hướng đầy đủ gồm $n$ đỉnh đánh số từ $1$ đến $n$: giữa hai đỉnh khác nhau bất kỳ $i$ và $j$ luôn có cung $i\to j$ với trọng số $a_{i,j}$ và cung $j\to i$ với trọng số $a_{j,i}$.

Người ta lần lượt xóa các đỉnh $x_1,x_2,\dots ,x_n$ khỏi đồ thị (xóa một đỉnh thì xóa luôn mọi cung đi vào và đi ra khỏi đỉnh đó). Trước mỗi lần xóa, hãy tính tổng độ dài đường đi ngắn nhất giữa mọi cặp có thứ tự $(u,v)$ các đỉnh còn lại trong đồ thị, trong đó đường đi chỉ được đi qua các đỉnh còn lại. Đường đi từ một đỉnh tới chính nó có độ dài $0$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên $a_{i,1},a_{i,2},\dots ,a_{i,n}$.
• Dòng cuối chứa $n$ số nguyên $x_1,x_2,\dots ,x_n$ là một hoán vị của $1,2,\dots ,n$.

Dữ liệu ra

In ra trên một dòng $n$ số nguyên, số thứ $t$ là tổng cần tính ngay trước khi xóa đỉnh $x_t$.

Ràng buộc

• $1\le n\le 150$
• $a_{i,i}=0$; với $i\ne j$: $1\le a_{i,j}\le {10}^5$

Ví dụ