有 $N$ 组人正在排队等待乘坐过山车。这些组按在队伍中的位置从 $1$ 到 $N$ 编号：第一组为 $1$，最后一组为 $N$。第 $i$ 组有 $a_i$ 个人。

过山车从时刻 $0$ 开始，在每个整数时刻出发。每辆过山车可以容纳 $0$ 到 $M$ 个人（含 $0$ 和 $M$）。

同一组的人必须乘坐同一辆过山车。每一组都希望尽可能早地乘坐过山车。因此，每一组人要么在能坐下的情况下一起进入过山车，否则就等待下一辆过山车。

你需要输出 $N$ 行。在第 $i$ 行中，输出第 $i$ 组人乘坐过山车的时刻。

输入格式

第一行包含两个整数 $N$ 和 $M$：组数和过山车的容量 ($1 \le N \le 10^5$; $1 \le M \le 10^9$)。

第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$：各组的人数 ($1 \le a_i \le M$)。

输出格式

输出 $N$ 行。在第 $i$ 行中，输出第 $i$ 组的答案。

样例

样例输入 1

3 5
2 4 1

样例输出 1

0
1
1

样例输入 2

2 1000000000
1000000000 1000000000

样例输出 2

0
1