الحد الزمني صارم بعض الشيء.

توجد $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