เวลาที่กำหนดค่อนข้างเข้มงวด

มีจุดที่แตกต่างกัน $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