Das Zeitlimit ist etwas knapp.

Auf einem Kreis liegen $n$ verschiedene Punkte, die im Uhrzeigersinn von $0$ bis einschließlich $n-1$ nummeriert sind. Ein Kreisabschnitt der Länge $\ell$ ($1 \le \ell \le n$) mit Anfang bei $i$ ($0 \le i \le n-1$) ist ein Tupel von $\ell$ im Uhrzeigersinn aufeinanderfolgenden Punkten, beginnend mit $i$ (also ein Tupel der Punkte mit den Nummern $i,(i+1)\bmod n,(i+2)\bmod n,\ldots,(i+\ell-1)\bmod n$). Kreisabschnitte der Länge $n$ mit Anfang bei $0,1,\ldots,n-1$ gelten als paarweise verschieden, obwohl sie dieselbe Punktmenge enthalten.

Jedem Kreisabschnitt sind ganzzahlige Kosten $c_{i,\ell}$ zugeordnet. Bestimmen Sie für jedes $k$ von $1$ bis $n$ die minimalen Gesamtkosten von genau $k$ Kreisabschnitten, sodass jeder der $n$ Punkte in genau einem von ihnen enthalten ist.

Beachten Sie, dass die Werte $c_{i,\ell}$ keine weiteren Eigenschaften erfüllen, außer dass sie vergleichsweise kleine positive ganze Zahlen sind. Das heißt, jedes $n\times n$-Feld ganzer Zahlen zwischen $1$ und $10^6$ ist ein gültiger Testfall für diese Aufgabe.

Eingabe

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 850$), die Anzahl der Punkte auf dem Kreis. Die $(i+1)$-te ($0 \le i \le n-1$) der folgenden $n$ Zeilen enthält $n$ durch Leerzeichen getrennte ganze Zahlen $c_{i,1},c_{i,2},\ldots,c_{i,n}$ ($1 \le c_{i,\ell} \le 10^6$ für $1 \le \ell \le n$).

Ausgabe

Geben Sie $n$ durch Leerzeichen getrennte ganze Zahlen aus. Die $k$-te Zahl soll die minimalen Gesamtkosten von $k$ Kreisabschnitten sein, die jeden Punkt genau einmal überdecken.

Beispiele

Eingabe 1

3
10 12 23
7 4 11
8 5 3

Ausgabe 1

3 12 25

Eingabe 2

1
15

Ausgabe 2

15