Batas waktunya agak ketat.

Terdapat $n$ titik berbeda pada sebuah lingkaran, yang diberi nomor dari $0$ hingga $n-1$ secara inklusif dalam urutan searah jarum jam. Segmen melingkar dengan panjang $\ell$ ($1 \le \ell \le n$) yang dimulai di $i$ ($0 \le i \le n-1$) adalah tupel berisi $\ell$ titik berurutan searah jarum jam, dimulai dari $i$ (dengan kata lain, tupel titik dengan nomor $i$, $(i+1) \bmod n$, $(i+2) \bmod n$, $\ldots$, $(i+\ell-1) \bmod n$). Segmen-segmen melingkar dengan panjang $n$ yang dimulai di $0, 1, \ldots, n-1$ dianggap berbeda satu sama lain, meskipun berisi himpunan titik yang sama.

Setiap segmen melingkar diberi biaya bilangan bulat $c_{i,\ell}$. Untuk setiap $k$ dari $1$ hingga $n$, carilah biaya total minimum dari tepat $k$ segmen melingkar sedemikian sehingga setiap titik dari $n$ titik tersebut termuat dalam tepat satu segmen.

Perhatikan bahwa nilai-nilai $c_{i,\ell}$ tidak memenuhi sifat apa pun selain berupa bilangan bulat positif yang relatif kecil. Artinya, sembarang larik bilangan bulat berukuran $n \times n$ dengan nilai antara $1$ dan $10^6$ merupakan kasus uji yang sah untuk soal ini.

Masukan

Baris pertama berisi bilangan bulat $n$ ($1 \le n \le 850$), yaitu jumlah titik pada lingkaran. Baris ke-$(i+1)$ ($0 \le i \le n-1$) dari $n$ baris berikutnya berisi $n$ bilangan bulat yang dipisahkan spasi, yaitu $c_{i,1}, c_{i,2}, \ldots, c_{i,n}$ ($1 \le c_{i,\ell} \le 10^6$ untuk $1 \le \ell \le n$).

Keluaran

Cetak $n$ bilangan bulat yang dipisahkan spasi: bilangan ke-$k$ harus berupa biaya total minimum dari $k$ segmen melingkar yang menutupi setiap titik tepat satu kali.

Contoh

Masukan 1

3
10 12 23
7 4 11
8 5 3

Keluaran 1

3 12 25

Masukan 2

1
15

Keluaran 2

15