El límite de tiempo es algo estricto.

Hay $n$ puntos distintos en una circunferencia, numerados de $0$ a $n-1$, ambos inclusive, en sentido horario. Un segmento circular de longitud $\ell$ ($1 \le \ell \le n$) que empieza en $i$ ($0 \le i \le n-1$) es una tupla de $\ell$ puntos consecutivos en sentido horario, empezando por $i$ (es decir, una tupla de puntos con números $i,(i+1)\bmod n,(i+2)\bmod n,\ldots,(i+\ell-1)\bmod n$). Los segmentos circulares de longitud $n$ que empiezan en $0,1,\ldots,n-1$ se consideran distintos entre sí, aunque contienen el mismo conjunto de puntos.

A cada segmento circular se le asigna un coste entero $c_{i,\ell}$. Para cada $k$ de $1$ a $n$, encuentra el coste total mínimo de exactamente $k$ segmentos circulares tales que cada uno de los $n$ puntos pertenezca exactamente a uno de ellos.

Ten en cuenta que los valores $c_{i,\ell}$ no cumplen ninguna propiedad, salvo ser enteros positivos relativamente pequeños. Es decir, cualquier matriz de $n \times n$ enteros entre $1$ y $10^6$ es un caso de prueba válido para este problema.

Entrada

La primera línea contiene un entero $n$ ($1 \le n \le 850$), el número de puntos de la circunferencia. La línea $(i+1)$-ésima ($0 \le i \le n-1$) de las siguientes $n$ líneas contiene $n$ enteros separados por espacios $c_{i,1},c_{i,2},\ldots,c_{i,n}$ ($1 \le c_{i,\ell} \le 10^6$ para $1 \le \ell \le n$).

Salida

Imprime $n$ enteros separados por espacios: el $k$-ésimo debe ser el coste total mínimo de $k$ segmentos circulares que cubran cada punto exactamente una vez.

Ejemplos

Entrada 1

3
10 12 23
7 4 11
8 5 3

Salida 1

3 12 25

Entrada 2

1
15

Salida 2

15