У Фермера Джона есть \(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 раза больше значений по умолчанию.**
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит \(N\) и \(K\). \(i+1\)-ая строка содержит высоту \(i\)-того стога.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите
\(N\) строк,
\(i\)-ая строка содержит высоту
\(i\)-го стога в решении.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
7
7
3
6
2
|
6
7
7
2
3
|