추상 원형 덮개

원 위에 서로 다른 $n$개의 점이 있으며, 시계 방향으로 $0$부터 $n - 1$까지 번호가 매겨져 있습니다. 길이가 $\ell$ ($1 \leq \ell \leq n$)이고 시작점이 $i$ ($0 \leq i \leq n - 1$)인 원형 구간은 시계 방향으로 연속된 $\ell$개의 점으로 이루어진 튜플입니다. 즉 $i, (i + 1) \bmod n, (i + 2) \bmod n, \ldots, (i + \ell - 1) \bmod n$ 입니다. 시작점이 $0, 1, \ldots, n - 1$인 길이 $n$의 원형 구간은 같은 점 집합을 포함하더라도 서로 다른 구간으로 봅니다.

각 원형 구간 $(i, \ell)$에는 정수 비용 $c_{i,\ell}$가 주어집니다. $1$부터 $n$까지의 각 $k$에 대해, 모든 점이 정확히 하나의 구간에 포함되도록 $k$개의 원형 구간을 골랐을 때 비용 합의 최솟값을 구하세요.

$c_{i,\ell}$는 비교적 작은 양의 정수라는 것 외에는 따로 만족해야 할 성질이 없습니다. $1$ 이상 $10^6$ 이하의 정수로 이루어진 $n \times n$ 배열이라면 모두 유효한 입력입니다.

시간 제한이 다소 빡빡합니다.

첫 줄에 점의 개수 $n$ ($1 \leq n \leq 850$)이 주어집니다. 이어지는 $n$개의 줄 중 $(i+1)$번째 줄에는 공백으로 구분된 정수 $c_{i,1}, c_{i,2}, \ldots, c_{i,n}$ ($1 \leq c_{i,\ell} \leq 10^6$, $1 \leq \ell \leq n$)이 주어집니다.

공백으로 구분된 정수 $n$개를 출력합니다. $k$번째 정수는 모든 점을 정확히 한 번씩 덮는 $k$개의 원형 구간 비용 합의 최솟값입니다.