在克罗什曾经住过的房子里,他有$$$n$$$个橱柜排成一排,第$$$i$$$个橱柜的高度为$$$h_i$$$。克罗什最近搬家了,但他没能一起搬橱柜。现在他想购买 $$$n$$$ 个新橱柜,以便它们看起来尽可能与旧橱柜相似。
Krosh 不记得橱柜的确切高度,但对于每三个连续的橱柜,他会记住其中最高和最矮的橱柜之间的高度差。换句话说,如果橱柜的高度为 $$$h_1, h_2, \ldots, h_n$$$,那么 Krosh 会记住所有 $$$1 的值 $$$w_i = \max(h_{i}, h_{i + 1}, h_{i + 2}) - \min(h_{i}, h_{i + 1}, h_{i + 2})$$$ \leq i \leq n - 2$$$。
Krosh 想购买这样的 $$$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}$$$) — 要购买的橱柜的高度,从左到右。
我们可以证明,如果有一个解,那么也存在一个满足高度约束的解。
如果有多个答案,请打印其中一个。
示例
输入 #1
7 20 4 8 12 16 20
输出 #1
YES 4 8 8 16 20 4 0
输入 #2
11 10 5 7 2 3 4 5 2 1 8
输出 #2
YES 1 1 6 8 6 5 2 0 0 1 8
输入 #3
6 9 1 6 9 0
输出 #3
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$$$。