| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 35 | 21 | 18 | 56.250% |
В некоторой стране есть $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