F. Прыжки по шкафам
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В доме Кроша стояло $$$n$$$ шкафов в линию, $$$i$$$-й шкаф имел высоту $$$h_i$$$. Недавно Крош переехал, но не смог перевезти с собой те самые шкафы. Ему хочется купить $$$n$$$ новых шкафов, чтобы те были как можно больше похожи на старые.

Крош не помнит конкретные высоты шкафов, но для каждой тройки подряд идущих шкафов он знает разность высот между самым высоким и самым низким из тройки. Иначе говоря, если последовательность высот шкафов была $$$h_1, h_2, \ldots, h_n$$$, то Крош помнит величины $$$w_i = \max(h_{i}, h_{i + 1}, h_{i + 2}) - \min(h_{i}, h_{i + 1}, h_{i + 2})$$$ для $$$1 \leq i \leq n - 2$$$.

В новый дом Крош хочет купить $$$n$$$ шкафов, так чтобы всё было как прежде: все значения $$$w_i$$$ должны сохраниться. Помогите Крошу понять, какие шкафы ему следует купить и в какой последовательности поставить, или определите, что он что-то перепутал, и такой последовательности шкафов не может быть.

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

В первой строке даны два целых числа $$$n$$$ и $$$C$$$ ($$$3 \leq n \leq 10^6$$$, $$$0 \leq C \leq 10^{12}$$$) — количество шкафов и ограничение на $$$w_i$$$.

Вторая строка содержит $$$n - 2$$$ целых числа $$$w_1, w_2, \ldots, w_{n - 2}$$$ ($$$0 \leq w_i \leq C$$$) — высоты шкафов слева направо.

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

Если не существует возможности купить $$$n$$$ шкафов, удовлетворяющих условиям, в единственной строке выведите «No».

Иначе в первой строке выведите «Yes», после чего во второй строке выведите $$$n$$$ целых чисел $$$h'_1, h'_2, \ldots, h'_n$$$ ($$$0 \le h'_i \le 10^{18}$$$) — высоты шкафов для покупки.

Можно показать, что если существует какое-то решение, то оно существует и при заданных ограничениях на высоты.

Если корректных решений несколько, выведите любое из них.

Примеры
Входные данные
7 20
4 8 12 16 20
Выходные данные
YES
4 8 8 16 20 4 0
Входные данные
11 10
5 7 2 3 4 5 2 1 8
Выходные данные
YES
1 1 6 8 6 5 2 0 0 1 8
Входные данные
6 9
1 6 9 0
Выходные данные
NO
Примечание

Рассмотрим первый пример:

  • $$$w_1 = \max(4, 8, 8) - \min(4, 8, 8) = 8 - 4 = 4$$$
  • $$$w_2 = \max(8, 8, 16) - \min(8, 8, 16) = 16 - 8 = 8$$$
  • $$$w_3 = \max(8, 16, 20) - \min(8, 16, 20) = 20 - 8 = 12$$$
  • $$$w_4 = \max(16, 20, 4) - \min(16, 20, 4) = 20 - 4 = 16$$$
  • $$$w_5 = \max(20, 4, 0) - \min(20, 4, 0) = 20 - 0 = 20$$$

Также корректным был бы, например, ответ с высотами: $$$0, 1, 4, 9, 16, 25, 36$$$