Ограничение по времени довольно жёсткое.

На окружности расположены $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$, $\ldots$, $(i+\ell-1) \bmod n$). Круговые отрезки длины $n$ с началами в $0, 1, \ldots, 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$) — количество точек на окружности. В $(i+1)$-й ($0 \le i \le n-1$) из следующих $n$ строк содержатся $n$ разделённых пробелами целых чисел $c_{i,1}, c_{i,2}, \ldots, 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