O limite de tempo é um pouco apertado.

Existem $n$ pontos distintos numa circunferência, numerados de $0$ a $n-1$, inclusive, no sentido dos ponteiros do relógio. Um segmento circular de comprimento $\ell$ ($1 \le \ell \le n$) com início em $i$ ($0 \le i \le n-1$) é um tuplo de $\ell$ pontos consecutivos no sentido dos ponteiros do relógio, começando em $i$ (por outras palavras, um tuplo de pontos com os números $i, (i+1) \bmod n, (i+2) \bmod n, \ldots, (i+\ell-1) \bmod n$). Os segmentos circulares de comprimento $n$ com início em $0, 1, \ldots, n-1$ são considerados distintos dois a dois, apesar de conterem o mesmo conjunto de pontos.

A cada segmento circular é atribuído um custo inteiro $c_{i,\ell}$. Para cada $k$ de $1$ a $n$, encontre o custo total mínimo de exatamente $k$ segmentos circulares tais que cada um dos $n$ pontos pertença a exatamente um deles.

Note que os valores $c_{i,\ell}$ não satisfazem nenhuma propriedade além de serem inteiros positivos relativamente pequenos. Ou seja, qualquer matriz $n \times n$ de inteiros entre $1$ e $10^6$ é um teste válido para este problema.

Entrada

A primeira linha contém um inteiro $n$ ($1 \le n \le 850$), o número de pontos na circunferência. A linha $(i+1)$ ($0 \le i \le n-1$) das $n$ linhas seguintes contém $n$ inteiros separados por espaços, $c_{i,1}, c_{i,2}, \ldots, c_{i,n}$ ($1 \le c_{i,\ell} \le 10^6$ para $1 \le \ell \le n$).

Saída

Imprima $n$ inteiros separados por espaços: o $k$-ésimo deve ser o custo total mínimo de $k$ segmentos circulares que cobrem cada ponto exatamente uma vez.

Exemplos

Entrada 1

3
10 12 23
7 4 11
8 5 3

Saída 1

3 12 25

Entrada 2

1
15

Saída 2

15