時間限制有點嚴格。

圓上有 $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