מגבלת הזמן מעט מחמירה.

על מעגל נמצאות $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