La limite de temps est un peu stricte.

Il y a $n$ points distincts sur un cercle, numérotés de $0$ à $n-1$ inclus dans le sens horaire. Un segment circulaire de longueur $\ell$ ($1 \le \ell \le n$) commençant en $i$ ($0 \le i \le n-1$) est un tuple de $\ell$ points consécutifs dans le sens horaire, à partir de $i$ (autrement dit, le tuple de points de numéros $i,(i+1)\bmod n,(i+2)\bmod n,\ldots,(i+\ell-1)\bmod n$). Les segments circulaires de longueur $n$ commençant en $0,1,\ldots,n-1$ sont considérés comme deux à deux différents, bien qu'ils contiennent le même ensemble de points.

Un coût entier $c_{i,\ell}$ est attribué à chaque segment circulaire. Pour chaque $k$ de $1$ à $n$, trouvez le coût total minimal d'exactement $k$ segments circulaires tels que chacun des $n$ points soit contenu dans exactement l'un d'entre eux.

Remarquez que les valeurs $c_{i,\ell}$ ne satisfont aucune propriété particulière, si ce n'est qu'elles sont des entiers strictement positifs relativement petits. Autrement dit, tout tableau $n\times n$ d'entiers compris entre $1$ et $10^6$ constitue un test valide pour ce problème.

Entrée

La première ligne contient un entier $n$ ($1 \le n \le 850$), le nombre de points sur le cercle. La $(i+1)$-ième ($0 \le i \le n-1$) des $n$ lignes suivantes contient $n$ entiers séparés par des espaces, $c_{i,1},c_{i,2},\ldots,c_{i,n}$ ($1 \le c_{i,\ell} \le 10^6$ pour $1 \le \ell \le n$).

Sortie

Affichez $n$ entiers séparés par des espaces : le $k$-ième doit être le coût total minimal de $k$ segments circulaires couvrant chaque point exactement une fois.

Exemples

Entrée 1

3
10 12 23
7 4 11
8 5 3

Sortie 1

3 12 25

Entrée 2

1
15

Sortie 2

15