11997 - K Smallest Sums

給定 k 組陣列，每個陣列有 k 個整數，從每個陣列中各取一個整數做加總共有 k^k 種可能的取法，本題請你找出總和最小的前 k 種取法的總和。

Input

輸入有許多測試資料，每一組測試資料有一整數k (2 <= k <= 750)，表示接下來有k列陣列，每個陣列有k個正整數，每個整數值不會超過1,000,000。輸入以EOF表示結束。

Output

請輸出每組資料的前k個最小的總合，以非遞減的順序列出。

Sample Input

3
1 8 5
9 2 5
10 7 6
2
1 1
1 2

Output for the Sample Input

9 10 12
2 2

---

原文出處