時間限制有啲嚴。

一個圓上面有 $n$ 個互不相同嘅點，按順時針方向由 $0$ 到 $n-1$ 編號（包括兩端）。一段由 $i$（$0 \le i \le n-1$）開始、長度係 $\ell$（$1 \le \ell \le n$）嘅圓弧段，係由 $i$ 開始、按順時針方向連續 $\ell$ 個點組成嘅元組（換句話講，就係編號為 $i,(i+1)\bmod n,(i+2)\bmod n,\ldots,(i+\ell-1)\bmod n$ 嘅點所組成嘅元組）。由 $0,1,\ldots,n-1$ 開始、長度係 $n$ 嘅圓弧段，雖然包含同一組點，但仍然視為兩兩唔同。

每段圓弧段都有一個整數費用 $c_{i,\ell}$。對每個由 $1$ 到 $n$ 嘅 $k$，求恰好 $k$ 段圓弧段嘅最小總費用，使得 $n$ 個點每個都恰好包含喺其中一段入面。

留意，除咗係相對細嘅正整數之外，$c_{i,\ell}$ 嘅值唔滿足任何其他性質。即係話，任何由 $1$ 到 $10^6$ 之間嘅整數組成嘅 $n \times n$ 陣列，都係呢題嘅合法測試。

輸入格式

第一行有一個整數 $n$（$1 \le n \le 850$），係圓上面嘅點數。之後 $n$ 行嘅第 $(i+1)$ 行（$0 \le i \le n-1$）有 $n$ 個以空格分隔嘅整數 $c_{i,1},c_{i,2},\ldots,c_{i,n}$（對 $1 \le \ell \le n$，有 $1 \le c_{i,\ell} \le 10^6$）。

輸出格式

輸出 $n$ 個以空格分隔嘅整數：第 $k$ 個應該係用 $k$ 段圓弧段恰好覆蓋每個點一次嘅最小總費用。

樣例

輸入格式 1

3
10 12 23
7 4 11
8 5 3

輸出格式 1

3 12 25

輸入格式 2

1
15

輸出格式 2

15