В некоторой стране есть $$$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