Обмеження часу досить суворе.

На колі розташовано $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