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

Имеются k массивов, каждый из которых содержит k целых чисел. Имеется k^k способов выбрать в точности один элемент из каждого массива и вычислить их сумму. Вам следует найти k наименьших сумм среди них.

Входные данные

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

Выходные данные

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

Примеры