Козак Вус — студент ВНЗ. У першому семестрі на нього чекає предметів та тижнів навчання. Вусу заздалегідь відомі всі завдання, і для зручності він оцінив їхню складність. Він склав таблицю розміром n \times m, де для -го предмета у -й тиждень потрібно виконати завдання складністю a_{i, j}. Зверніть увагу, що всі значення складності є попарно різними числами у всій таблиці.
Складністю тижня Вус називає сумарну складність завдань з усіх предметів у цей тиждень.
Вусу не вистачило канікул для відпочинку, тож він хоче хоча б на початку семестру не сильно напружуватися. На щастя, саме цього року студентам дозволили коригувати план навчання. У Вуса є можливість не більше разів виконати таку операцію: вибрати певний предмет та два різні тижні j_1 і j_2, після чого поміняти місцями завдання з цього предмета. Таким чином, у таблиці числа a_{i, j_1} та a_{i, j_2} обмінюються значеннями.
Мета Вуса — зробити так, щоб складність першого тижня була якомога меншою. Якщо таких варіантів декілька, він хоче мінімізувати складність другого тижня. Якщо ж і таких варіантів декілька — мінімізувати складність третього тижня, і так далі.
Більш формально, нехай b_j — це складність -го тижня:
Козак Вус хоче застосувати не більше операцій так, щоб результуючий масив тижневих складностей B = [b_1, b_2, \dots, b_m] став лексикографічно мінімальним. Допоможіть йому знайти цей масив.
Перший рядок містить три цілі числа , , (1 \le n, m \le 1000, 0 \le k \le 10^9) — кількість рядків, кількість стовпців та максимальна кількість операцій.
Наступні рядків містять по цілих чисел a_{i,j} (1 \le a_{i,j} \le 10^6, усі числа a_{i,j} попарно різні) — початкову таблицю.
Виведіть цілих чисел — лексикографічно найменший масив сум стовпців, який можна отримати після не більше ніж операцій.
Приклад 1
Приклад 2
Для першого тестового прикладу:
Оскільки k = 1, можна виконати не більше однієї операції.
Початкові суми стовпців дорівнюють:
7 + 6 + 5 = 18,
1 + 8 + 2 = 11,
3 + 4 + 9 = 16.
Тобто початковий масив сум дорівнює [18, 11, 16].
Щоб отримати лексикографічно найменший масив, найкраще виконати операцію в першому рядку та поміняти місцями числа і .
Після цього таблиця матиме вигляд:
перший рядок: ,
другий рядок: ,
третій рядок: .
Суми стовпців дорівнюють:
1 + 6 + 5 = 12,
7 + 8 + 2 = 17,
3 + 4 + 9 = 16.
Отриманий масив [12, 17, 16] є лексикографічно найменшим з усіх варіантів, які можна отримати за одну операцію.
Для другого тестового прикладу:
Початкові суми стовпців дорівнюють:
9 + 2 + 5 = 16,
1 + 8 + 6 = 15,
7 + 3 + 11 = 21,
4 + 10 + 12 = 26.
Початковий масив сум дорівнює [16, 15, 21, 26].
Виконаємо операцію в першому рядку та поміняємо місцями числа і , після чого виконаємо другу операцію і поміняємо місцями числа і так само у першому рядку. Тоді отримаємо наступну таблицю:
Суми стовпців дорівнюють [8, 18, 21, 31].
( бали): k=n\cdot m;
( балів): k=1, n=1;
( балів): n=1;
( балів): елементи у рядках початково відсортовані за спаданням;
( балів): k \le 10;
( балів): m=2;
( балів): n, m \le 100;
( балів): без додаткових обмежень.