J. Поиск и замена
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть последовательность $$$a$$$, состоящая из $$$n$$$ целых чисел.

Поликарп может производить со своей последовательностью следующие операции:

  • найти в своем массиве максимум (если максимумов несколько, нужно найти самый левый максимум);
  • найти в своем массиве минимум (если минимумов несколько, нужно найти самый правый минимум);
  • заменить оба найденных элемента на их среднее арифметическое, округленное вниз к ближайшему целому числу.

Например, если найденный максимум равен $$$10$$$, а найденный минимум равен $$$3$$$, то оба найденных элемента будут заменены на число $$$6$$$, а если найденный максимум равен $$$11$$$, а найденный минимум равен $$$7$$$, то оба найденных элемента будут заменены на число $$$9$$$.

Перед вами стоит задача определить, как будет выглядеть последовательность Поликарпа, если к ней последовательно применить ровно $$$k$$$ описанных операций.

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

В первой строке следуют два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le k \le n$$$) — количество элементов в последовательности Поликарпа и количество операций.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно $$$i$$$-му элементу последовательности Поликарпа.

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

Выведите $$$n$$$ целых чисел, причем $$$i$$$-е выведенное число должно быть равно $$$i$$$-му элементу в последовательности Поликарпа после последовательного применения $$$k$$$ описанных операций.

Примеры
Входные данные
5 2
3 7 4 7 5
Выходные данные
5 5 5 5 5
Входные данные
6 1
4 4 4 19 19 19
Выходные данные
4 4 11 11 19 19
Входные данные
10 3
5 8 3 1 11 4 14 11 1 15
Выходные данные
5 8 7 7 7 4 7 11 8 8
Примечание

В первом примере в ходе первой операции будет найден максимум в позиции $$$2$$$ и минимум в позиции $$$1$$$. Среднее арифметическое найденных чисел равно $$$5$$$, поэтому после первой операции последовательность станет равна $$$[5, 5, 4, 7, 5]$$$. В ходе второй операции будет найден максимум в позиции $$$4$$$ и минимум в позиции $$$3$$$. Среднее арифметическое найденных чисел, округленное вниз, равно $$$5$$$, поэтому после второй операции последовательность станет равна $$$[5, 5, 5, 5, 5]$$$.

Во втором примере в ходе первой операции будет найден максимум в позиции $$$4$$$ и минимум в позиции $$$3$$$. Среднее арифметическое найденных чисел, округленное вниз, равно $$$11$$$, поэтому после первой операции последовательность станет равна $$$[4, 4, 11, 11, 19, 19]$$$.