Limit czasu jest dość wymagający.

Na okręgu znajduje się $n$ różnych punktów, ponumerowanych od $0$ do $n-1$ włącznie, zgodnie z ruchem wskazówek zegara. Odcinek kołowy o długości $\ell$ ($1 \le \ell \le n$), rozpoczynający się w $i$ ($0 \le i \le n-1$), to krotka $\ell$ kolejnych punktów w porządku zgodnym z ruchem wskazówek zegara, zaczynająca się od $i$ (innymi słowy, krotka punktów o numerach $i, (i+1) \bmod n, (i+2) \bmod n, \ldots, (i+\ell-1) \bmod n$). Odcinki kołowe o długości $n$, rozpoczynające się w $0, 1, \ldots, n-1$, uważa się za parami różne, mimo że zawierają ten sam zbiór punktów.

Każdemu odcinkowi kołowemu przypisany jest całkowity koszt $c_{i,\ell}$. Dla każdego $k$ od $1$ do $n$ znajdź minimalny łączny koszt dokładnie $k$ odcinków kołowych takich, że każdy z $n$ punktów należy do dokładnie jednego z nich.

Zauważ, że wartości $c_{i,\ell}$ nie spełniają żadnych dodatkowych własności poza tym, że są stosunkowo małymi dodatnimi liczbami całkowitymi. Oznacza to, że dowolna tablica $n \times n$ liczb całkowitych od $1$ do $10^6$ jest poprawnym testem dla tego zadania.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ ($1 \le n \le 850$) — liczbę punktów na okręgu. Wiersz $(i+1)$-szy ($0 \le i \le n-1$) spośród kolejnych $n$ wierszy zawiera $n$ liczb całkowitych oddzielonych spacjami: $c_{i,1}, c_{i,2}, \ldots, c_{i,n}$ ($1 \le c_{i,\ell} \le 10^6$ dla $1 \le \ell \le n$).

Wyjście

Wypisz $n$ liczb całkowitych oddzielonych spacjami: $k$-ta z nich powinna być minimalnym łącznym kosztem $k$ odcinków kołowych pokrywających każdy punkt dokładnie raz.

Przykład

Wejście 1

3
10 12 23
7 4 11
8 5 3

Wyjście 1

3 12 25

Wejście 2

1
15

Wyjście 2

15