시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB14101071.429%

문제

В некоторой стране есть $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$>>, если это невозможно.

예제 입력 1

3 3
1 2 1

예제 출력 1

1
0
1

예제 입력 2

3 4
1 2 1

예제 출력 2

2
1
2

예제 입력 3

3 4
1 3 5

예제 출력 3

1
0
-1