У Фермера Джона є \(N\) (\(1\leq N \leq 10^5\)) стогів з тюків сіна. Для кожного \(i\in [1,N]\), \(i\)-ий стог має \(h_i\) (\(1\le h_i\le 10^9\)) тюків. Бессі може виконувати такі операції:

• Якщо висоти двох сусідніх стогів сіна розрізняються не більше ніж на \(K\) (\(1\le K\le 10^9\)), вона може поміняти місцями два стоги

Яку лексикографічно мінімальну послідовність висот Бесі може отримати після деякої послідовності таких операцій?

Примітка: обмеження на час та пам'ять для цього завдання 4сек та 512 Мбт, що в 2 рази більше значень за замовчуванням.

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

Перший рядок введення містить \(N\) та \(K\). \(i+1\)-ий рядок містить висоту \(i\)-того стога.

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

Виведіть \(N\) рядків, \(i\)-ий рядок містить висоту \(i\)-го стога у вирішенні.

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

5 3
7
7
3
6
2

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

6
7
7
2
3

Один із способів, яким Бєсі може змінювати стоги такий:

    7 7 3 6 2
    7 7 6 3 2
    7 7 6 2 3
    7 6 7 2 3
    6 7 7 2 3