D. R2-D2 и армия дроидов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Армия из n дроидов построена в один ряд. Каждый дроид описывается m целыми числами a1, a2, ..., am, где ai — количество деталей i-го типа в механизме этого дроида. R2-D2 хочет уничтожить максимальную по длине последовательность подряд идущих дроидов. У него есть m оружий, i-е из них способно за один выстрел уничтожить у всех дроидов в армии по одной детали i-го типа (если у дроида нет деталей этого типа, то ничего не происходит).

Дроид считается уничтоженным, когда уничтожены все его детали. R2-D2 может сделать не больше k выстрелов. Сколько выстрелов из оружия каждого типа нужно произвести R2-D2, чтобы уничтожить максимальную по длине последовательность подряд идущих дроидов?

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

В первой строке записано три целых числа n, m, k (1 ≤ n ≤ 105, 1 ≤ m ≤ 5, 0 ≤ k ≤ 109) — количество дроидов, количество типов деталей и количество доступных выстрелов соответственно.

Далее идут n строк, описывающие дроидов. Каждая строка содержит m целых чисел a1, a2, ..., am (0 ≤ ai ≤ 108), где ai — количество деталей i-го типа у соответствующего робота.

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

Выведите через пробел m целых чисел, где i-е число — количество выстрелов из оружия i-го типа, которые нужно произвести, чтобы уничтожить максимальную по длине последовательность подряд идущих дроидов.

Если существует несколько оптимальных ответов — выведите любой.

Необязательно совершать ровно k выстрелов, можно совершить меньше.

Примеры
Входные данные
5 2 4
4 0
1 2
2 1
0 2
1 3
Выходные данные
2 2
Входные данные
3 2 4
1 2
1 3
2 2
Выходные данные
1 3
Примечание

В первом тесте будут уничтожены второй, третий и четвертый дроиды.

Во втором тесте будут уничтожены первый и второй дроиды.