K найменших сум

Маємо k масивів, кожен з яких містить k цілих чисел. Існує k^k способів вибрати рівно один елемент з кожного масиву і обчислити їхню суму. Ваше завдання — знайти k найменших сум серед цих можливих.

Вхідні дані

Вхідні дані складаються з кількох тестів. Перша стрічка кожного тесту містить ціле число k (2 ≤ k ≤ 750). Кожна з наступних k стрічок описує вміст одного масиву — k натуральних чисел. Кожне число не перевищує 1,000,000.

Вихідні дані

Для кожного тесту виведіть в окремому рядку k найменших сум у порядку зростання.

Приклади