実行時間制限はやや厳しめです。

円周上に相異なる $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$ について、$n$ 個の点がそれぞれちょうど 1 つの区間に含まれるような、ちょうど $k$ 個の円周区間のコストの総和の最小値を求めてください。

$c_{i,\ell}$ の値には、比較的小さい正の整数であること以外の性質はない点に注意してください。つまり、$1$ から $10^6$ までの整数からなる任意の $n\times n$ の配列が、この問題の有効なテストケースになります。

入力

1 行目には、円周上の点の数を表す整数 $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$ 番目は、すべての点をそれぞれちょうど 1 回覆う $k$ 個の円周区間のコストの総和の最小値でなければなりません。

入出力例

入力 1

3
10 12 23
7 4 11
8 5 3

出力 1

3 12 25

入力 2

1
15

出力 2

15