你是 $K$ 个苹果的骄傲拥有者。你想把它们作为遗产留给你的子女和孙辈。你有 $N$ 个子女。这些子女中的每一个都有自己的孩子。数组 $grand[]$ 描述了这一点：它的第 $i$ 个值等于你的第 $i$ 个子女拥有的孩子数量。因此，你的孙辈总数等于 $grand[1] + grand[2] + \dots + grand[N]$。保证对于所有 $1 \le i \le N$，都有 $grand[i] \ge 1$。

你必须决定给每个子女多少个苹果。你必须分发所有的 $K$ 个苹果，不能有剩余。此外，你只能分发整数个苹果。在你将苹果分给子女后，他们会把苹果重新分配给他们的孩子。因为你想尽可能公平，所以你想找到最小的 $DIFF$ 值，使得：

• 分给子女的苹果数量的最大值与最小值之差不超过 $DIFF$。
• 分给孙辈的苹果数量的最大值与最小值之差不超过 $DIFF$。

因为你的子女也很公平，你可以假设他们会以使 $DIFF$ 尽可能小的方式重新分配分给他们的苹果。然而，决定给每个直系子女多少个苹果取决于你。

输出最小的可能 $DIFF$ 值，以及为达到该值而分给每个子女的苹果数量。

输入格式

第一行包含两个整数 $N$ 和 $K$ ($1 \le N \le 1\,000\,000, 1 \le K \le 10^{18}$)。 第二行包含 $N$ 个整数，其中第 $i$ 个是 $grand[i]$。孙辈总数不超过 $2 \cdot 10^9$。

输出格式

第一行必须包含 $DIFF$ 的值。第二行必须包含 $N$ 个非负整数：分给每个子女的苹果数量。这些整数之和必须等于 $K$。任何能达到正确 $DIFF$ 值的分配方案均可被接受。

样例

输入 1

2 100
1 2

输出 1

15
43 57

说明

如果你给第一个子女 43 个苹果，给第二个子女 57 个苹果，他们会按以下方式分配：第一个子女会将全部 43 个苹果给他唯一的孩子。第二个子女会给她的一个孩子 28 个苹果，给另一个孩子 29 个苹果。

子女收到的苹果数量的最大差值为 $57 - 43 = 14$。孙辈收到的苹果数量的最大差值为 $43 - 28 = 15$。