Армия из n дроидов построена в один ряд. Каждый дроид описывается m целыми числами a1, a2, ..., am, где ai — количество деталей i-го типа в механизме этого дроида. R2-D2 хочет уничтожить максимальную по длине последовательность подряд идущих дроидов. У него есть m оружий, i-е из них способно за один выстрел уничтожить у всех дроидов в армии по одной детали i-го типа (если у дроида нет деталей этого типа, то ничего не происходит).
Дроид считается уничтоженным, когда уничтожены все его детали. R2-D2 может сделать не больше k выстрелов. Сколько выстрелов из оружия каждого типа нужно произвести R2-D2, чтобы уничтожить максимальную по длине последовательность подряд идущих дроидов?
Выходные данные
Выведите через пробел m целых чисел, где i-е число — количество выстрелов из оружия i-го типа, которые нужно произвести, чтобы уничтожить максимальную по длине последовательность подряд идущих дроидов.
Если существует несколько оптимальных ответов — выведите любой.
Необязательно совершать ровно k выстрелов, можно совершить меньше.
Примечание
В первом тесте будут уничтожены второй, третий и четвертый дроиды.
Во втором тесте будут уничтожены первый и второй дроиды.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2 4
4 0
1 2
2 1
0 2
1 3
|
2 2
|
|
2
|
3 2 4
1 2
1 3
2 2
|
1 3
|