最近为波利卡普买了一只狗。这只狗的名字叫科门。现在波利卡普有很多麻烦。例如,科门喜欢散步。
根据Polycarp的经验,狗需要连续两天至少k次散步才能感觉良好。例如,如果 k = 5,昨天 Polycarp 和 Cormen 一起散步了 2 次,那么今天他必须至少出去散步 3 次。
波利卡普分析了他接下来 n 天的所有事务,并制作了一个由 n 个整数 a1, a2, ..., an 组成的序列,其中 ai 是波利卡普在第 i 天处理他所有事务时带着狗散步的次数(例如,他必须去商店、扔垃圾等)。
帮助波利卡普确定他在接下来的 n 天内需要额外进行的最少步行次数,以便科门在这 n 天内感觉良好。您可以假设在第一天的前一天和第 n 天的后一天,波利卡普将与科门一起散步恰好 k 次。
编写一个程序,找出额外散步的最少次数和适当的时间表——整数序列 b1, b2, ..., bn (bi ≥ ai),其中 bi 表示第 i 天与狗一起散步的总数。
输入
第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 500) — 任意连续两天与 Cormen 一起散步的天数和最小次数。
第二行包含整数 a1, a2, ..., an (0 ≤ ai ≤ 500) – 波利卡普已计划的第 i 天与 Cormen 一起散步的次数。
输出
在第一行中打印 Polycarp 在接下来的 n 天内应该进行的最少额外步行次数,以便 Cormen 在所有日子里都感觉良好。
在第二行中打印 n 个整数 b1, b2, ..., bn,其中 bi - 根据找到的解决方案在第 i 天步行的总数(对于从 1 到 n 的所有 i,ai ≤ bi)。如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
3 5 2 0 1
输出 #1
4 2 3 2
输入 #2
3 1 0 0 0
输出 #2
1 0 1 0
输入 #3
4 6 2 4 3 5
输出 #3
0 2 4 3 5