Задача F2. Жадная последовательность

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

Дана последовательность из N целых чисел ai. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.

Требуется написать программу, выводящую последовательность, которая получится после выполнения M операций.

Формат входного файла

Первая строка входного файла содержит целые числа N и M — количество элементов последовательности и количество операций.

Вторая строка входного файла содержит N целых чисел ai — элементы последовательности.

Формат выходного файла

В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.

Ограничения

1 ≤ M < N ≤ 105

 − 104 ≤ ai ≤ 104

Описание подзадач и системы оценивания

Баллы за подзадачи 1,2 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 3 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
nm
1202 ≤ n ≤ 5m < nполная
2202 ≤ n ≤ 1000m < n1полная
3602 ≤ n ≤ 105m < n1,2полная

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1
1 2 3 4
3 4 3
2
4 2
3 2 1 1
3 4

0.105s 0.022s 15