2099. СМС

Одним из самых популярных способов использования мобильной связи являются СМС-сообщения. Каждый день миллионы людей отправляют десятки миллионов сообщений: "Привет!", "Как дела?", "Ты где?", "Я задержусь" и еще тысячи различных коротких посланий.

К сожалению, на клавиатуре мобильного телефона может оказаться меньше кнопок, чем букв в алфавите. Поэтому на первой кнопке размещаются несколько первых букв алфавита, на второй – следующие несколько и так далее. Чтобы набрать некую букву, необходимо нажать ту кнопку, на которой она размещена, `t` раз, если буква является `t`-ой по алфавиту, размещенной на этой кнопке. Так, если на первой кнопке клавиатуры размещены буквы 'a', 'b' и 'c', то для выбора буквы 'c' придется нажать эту кнопку трижды.

Ученые изучили среднее количество раз, которое каждая буква алфавита встречается в СМС-ках за время службы среднестатистического телефона. Теперь у фирмы-производителя появилась возможность спроектировать клавиатуру так, чтобы минимизировать суммарное количество нажатий на все кнопки. Помогите им сделать это.

Первая строка входного файла содержит два целых числа `n` и `m` (`1\ ≤\ n\ ≤\ 30`, `1\ ≤\ m\ ≤\ 10`) – количество букв в алфавите и кнопок на клавиатуре телефона.

Следующая строка содержит `n` целых чисел `a_i` (`0\ ≤\ a_i\ ≤\ 1\ 000\ 000`) – количество раз, которые будет напечатана `i`-ая буква алфавита.

В выходной файл выведите `m` целых неотрицательных чисел `b_i` – количество букв, отнесенных к `i`-ой кнопке клавиатуры. Сумма всех `b_i` должна быть равна `n`.

Если возможных ответов несколько – выведите любой.

5 3
1 3 5 1 1

1 1 3

В примере на первой кнопке размещена одна первая буква алфавита, на второй – только вторая, а на третьей – оставшиеся три.

Таким образом, суммарное количество нажатий на кнопки будет: `1\ *\ 1\ +\ 3\ *\ 1\ +\ 5\ *\ 1\ +\ 1\ *\ 2\ +\ 1\ *\ 3\ =\ 14`.