Магічні кульки Містера А

Містер А знайшов у своїй шафі послідовність з $n$ магічних кульок. Всі ці магічні кульки є кульками різного кольору, для зручності кольори пронумеровано цілими числами від $1$ до $n$. Звісно у Містера А кількість кульок парна.

Також, у Містера А є масив цілих чисел $Q$, куди він записуватиме кольори кульок. Початково масив $Q$ порожній.

Містер А планує виконати $\frac{n}{2}$ операцій наступного виду: герой вибиратиме пару кульок, які є сусідніми у послідовності, видалятиме їх з послідовності та додаватиме кольори видалених кульок у початок масиву $Q$. Кульки, що видаляються, матимуть такий самий відносний порядок у масиві $Q$ як і у початковій послідовності. Після видалення елементів з послідовності дві частини послідовності з'єднуються, утворюючи при цьому одну нову послідовність.

Наприклад, якщо послідовність кольорів кульок рівна $\left\{1,5,3,2,6,4\right\}$, можна спочатку додати до початку масиву $Q$ пару елементів $\left\{2,6\right\}$, після чого додати пару елементів $\left\{3,4\right\}$, і наприкінці додати пару елементів $\left\{1,5\right\}$ — утворений масив $Q$ буде рівним $[1,5,3,4,2,6]$.

Тепер Містеру А цікаво, який лексикографічно мінімальний масив $Q$ можна отримати виконавши $\frac{n}{2}$ операцій. Нагадаємо, що лексикографічний порядок задається наступним чином. Нехай маємо два масиви. Знайдемо першу позицію, у якій елементи двох масивів відрізняються. Тоді якщо на цій позиції елемент першого масиву менший за елемент другого, то перший масив лексикографічно менший за другий, інакше "— навпаки, перший масив більший за другий. Наприклад, виконуються наступні нерівності: $[10,3,1]$ < $[10,4,5]$, $[1,1,1]<[1,2,3],[1,2,3]<[10,10,10]$.

Допоможіть Містеру А знайти $k$ перших елементів мінімально можливого масиву $Q$.

Вхідні дані

Перший рядок містить два цілі числа $n$ та $k$ $(1\le k\le n\le 10^6)$. Гарантується, що $n$ — парне.

Другий рядок містить $n$ різних цілих чисел $a_1,a_2,\dots ,a_n$ $(1\le a_i\le n)$ — кольори кульок послідовності.

Вихідні дані

Виведіть $k$ цілих чисел $q_1,q_2,\dots ,q_k$ — перші елементи мінімально можливого масиву $Q$.

Приклади

Оцінювання

1. ($8$ балів): $n\le 10^5,k=1$;

2. ($5$ балів): $n\le 10^5,k=2$;

3. ($19$ балів): $n\le 14$;

4. ($16$ балів): $n\le 10^3$;

5. ($10$ балів): $n\le 10^5,k\le 20$;

6. ($24$ бали): $n\le 10^5$;

7. ($18$ балів): без додаткових обмежень.