Вам надано масив із ~n~ цілих чисел. Ваше завдання — обчислити медіану кожного вікна з ~k~ елементів, зліва направо.

Медіана є середнім елементом під час сортування елементів. Якщо число елементів парне, можливі дві медіани, і ми припускаємо, що медіана є меншою з них.

Обмеження

• ~1≤k≤n≤2⋅10^5~
• ~1≤x_i ​ ≤10^9~

Формат вхідних даних

Перший рядок містить два цілі числа ~n~ і ~k~: кількість елементів і розмір вікна.

Потім є ~n~ цілих чисел ~x_1 ​ , x_2 ​ ,…, x_n~ ​ : вміст масиву.

Формат вихідних даних

Вивести ~n-k+1~ значень: медіани відповідних підмасивів.

Приклад вхідних даних

8 3
2 4 3 5 8 1 2 1

Приклад вихідних даних

3 4 5 5 2 1