Giới hạn thời gian hơi chặt.

Có $n$ điểm phân biệt trên một đường tròn, được đánh số từ $0$ đến $n-1$ theo chiều kim đồng hồ. Một đoạn tròn có độ dài $\ell$ ($1 \le \ell \le n$) bắt đầu tại $i$ ($0 \le i \le n-1$) là một bộ gồm $\ell$ điểm liên tiếp theo chiều kim đồng hồ, bắt đầu từ $i$ (nói cách khác, đó là bộ các điểm có số hiệu $i,(i+1)\bmod n,(i+2)\bmod n,\ldots,(i+\ell-1)\bmod n$). Các đoạn tròn có độ dài $n$ bắt đầu tại $0,1,\ldots,n-1$ được coi là đôi một khác nhau, mặc dù chúng chứa cùng một tập hợp điểm.

Mỗi đoạn tròn được gán một chi phí nguyên $c_{i,\ell}$. Với mỗi $k$ từ $1$ đến $n$, hãy tìm tổng chi phí nhỏ nhất của đúng $k$ đoạn tròn sao cho mỗi điểm trong $n$ điểm thuộc đúng một đoạn trong số đó.

Lưu ý rằng các giá trị $c_{i,\ell}$ không thỏa mãn tính chất nào ngoài việc là các số nguyên dương tương đối nhỏ. Nghĩa là mọi mảng số nguyên kích thước $n\times n$ với các phần tử từ $1$ đến $10^6$ đều là một bộ kiểm thử hợp lệ cho bài toán này.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 850$), số điểm trên đường tròn. Dòng thứ $(i+1)$ ($0 \le i \le n-1$) trong $n$ dòng tiếp theo chứa $n$ số nguyên cách nhau bởi dấu cách $c_{i,1},c_{i,2},\ldots,c_{i,n}$ ($1 \le c_{i,\ell} \le 10^6$ với $1 \le \ell \le n$).

Dữ liệu ra

In $n$ số nguyên cách nhau bởi dấu cách: số thứ $k$ phải là tổng chi phí nhỏ nhất của $k$ đoạn tròn phủ mỗi điểm đúng một lần.

Ví dụ

Dữ liệu vào 1

3
10 12 23
7 4 11
8 5 3

Dữ liệu ra 1

3 12 25

Dữ liệu vào 2

1
15

Dữ liệu ra 2

15