Alice 有一个序列 $a_1, a_2, \dots, a_n$。请帮助 Alice 构造一个新的序列 $b_1, b_2, \dots, b_n$，使得：

• 令 $c_i = a_i + c_{i-1} + b_i$，其中 $c_0 = 0$ 且对于所有 $1 \le i \le n$ 满足 $0 \le c_i \le m$。
• 序列 $b_1, b_2, \dots, b_n$ 中非零元素的个数尽可能少。

输入格式

输入包含多个测试用例。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 10^6, 1 \le m \le 10^9$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($|a_i| \le m$)。

所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($|b_i| \le 10^{18}$)，表示你为 Alice 构造的序列。序列 $b_1, b_2, \dots, b_n$ 中的非零元素个数必须尽可能少。如果存在多种方案，输出其中任意一种即可。

样例

样例输入 1

5 3
1 2 3 3 3
5 5
3 0 5 -3 -2

样例输出 1

0 0 -6 0 -5
0 0 -3 0 0