圆周上有 $n$ 个不同的点，按顺时针方向编号为 $0$ 到 $n-1$。长度为 $\ell$ ($1 \le \ell \le n$)、起点为 $i$ ($0 \le i \le n-1$) 的圆弧段是一个包含 $\ell$ 个顺时针连续点的元组，以 $i$ 开头（换句话说，即包含编号为 $i, (i+1) \bmod n, (i+2) \bmod n, \dots, (i+\ell-1) \bmod n$ 的点的元组）。长度为 $n$ 且起点分别为 $0, 1, \dots, n-1$ 的圆弧段被视为互不相同，尽管它们包含的点集相同。

每个圆弧段都被赋予一个整数代价 $c_{i, \ell}$。对于每个 $k$ 从 $1$ 到 $n$，求出恰好使用 $k$ 个圆弧段覆盖所有 $n$ 个点，且每个点恰好被覆盖一次的最小总代价。

注意，除了 $c_{i, \ell}$ 是相对较小的正整数外，这些值没有任何其他性质。也就是说，任何 $n \times n$ 的整数数组（元素在 $1$ 到 $10^6$ 之间）对于本题都是合法的测试数据。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 850$)，表示圆上的点数。接下来的 $n$ 行中，第 $(i+1)$ 行（$0 \le i \le n-1$）包含 $n$ 个空格分隔的整数 $c_{i, 1}, c_{i, 2}, \dots, c_{i, n}$ ($1 \le c_{i, \ell} \le 10^6$，其中 $1 \le \ell \le n$)。

输出格式

输出 $n$ 个空格分隔的整数：其中第 $k$ 个整数表示恰好使用 $k$ 个圆弧段覆盖所有点且每个点恰好被覆盖一次的最小总代价。

样例

样例输入 1

3
10 12 23
7 4 11
8 5 3

样例输出 1

3 12 25

样例输入 2

1
15

样例输出 2

15