Туристы, достопримечательности и телескопы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В некоторой стране есть $$$N$$$ городов, расположенных на одной прямой. В каждом городе находится по $$$s_i$$$ достопримечательностей.

Чтобы туристы могли любоваться не только достопримечательностями одного города, компания X-tensive решила установить в каждом городе по телескопу. Однако никто не хочет, чтобы туристы могли видеть больше $$$R$$$ достопримечательностей из одного города, иначе они не захотят посещать другие города. Для этого можно отрегулировать силу у каждого телескопа. Сила «$$$0$$$» означает, что туристы могут наблюдать только достопримечательности города, где находится этот телескоп, сила «$$$1$$$»  — туристы могут увидеть достопримечательности ещё и соседних городов, сила «$$$2$$$»  — вдобавок идут соседи этих соседей и так далее. Конечно же, сила телескопа в городе не должна быть настолько большой, чтобы обзор выходил за пределы страны в обоих направлениях.

После долгих обсуждений компания X-tensive приняла решение поставить максимальную возможную силу у каждого телескопа, но так, чтобы она удовлетворяла всем требованиям. Ответьте, какую силу нужно установить для каждого телескопа, либо «$$$-1$$$», если это невозможно.

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

В первой строке вводятся через пробел два целых числа $$$N$$$ и $$$R$$$  — количество городов в стране и ограничение на количество видимых достопримечательностей из одного города $$$(3 \le N \le 10^5$$$, $$$1 \le R \le 10^{14})$$$.

В следующей строке вводится $$$N$$$ целых чисел $$$s_i$$$ через пробел  — количество достопримечательностей в каждом из городов в порядке их расположения на прямой $$$(1 \le s_i \le 10^9)$$$.

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

Выведите $$$N$$$ строк. В $$$i$$$-й строке выведите силу телескопа в $$$i$$$-м городе, удовлетворяющую всем условиям, либо «$$$-1$$$», если это невозможно.

Примеры

Входные данные
3 3
1 2 1
Выходные данные
1
0
1
Входные данные
3 4
1 2 1
Выходные данные
2
1
2
Входные данные
3 4
1 3 5
Выходные данные
1
0
-1