[AdditionalFile5385.zip](file://AdditionalFile5385.zip?type=additional_file)

#5385. 「OOI 2021 Day 1」跳跃橱柜

标签: 传统 | 时间限制: 6000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2021 Day1 T1 「Прыжки по шкафам」。

在克罗什的家中，曾经有 $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 \leq h'_i \leq 10^{18})$，表示要购买的橱柜的高度。

可以证明，如果存在解，则在给定高度限制下一定存在一个解。

如果存在多个正确解，可以输出其中任意一个。

样例 1

输入

7 20
4 8 12 16 20

输出

Yes
4 8 8 16 20 4 0

以第一个样例为例：

• $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$ 的序列也是一个正确解。

样例 2

输入

11 10
5 7 2 3 4 5 2 1 8

输出

Yes
1 1 6 8 6 5 2 0 0 1 8

样例 3

输入

6 9
1 6 9 0

输出

No

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。