说明

在日本娱乐集团 (JAG) 中，成员们讨论如何提供更好的娱乐体验以吸引更多人。最近，他们对减少排队等待时间带来的压力很感兴趣。

作为 JAG 的一员，你发现了一个假设：了解等待时间可以减少这种压力。因此，你决定编写一个程序来预估过山车的等待时间。

有 $N$ 个组在过山车前排队，组号从 $1$ 到 $N$。第 $i$ 组有 $a_i$ 个人。排队的人按照组号升序乘坐过山车。

第一辆过山车在时间 $0$ 出发，之后每分钟出发一辆。过山车最多可以容纳 $M$ 个人。

对于每个组，整个组的成员必须在同一时间乘坐过山车。此外，一次乘坐并不需要恰好坐满 $M$ 个人。每个组都希望尽快乘坐过山车，因此只要条件允许，他们就会乘坐。

你需要输出 $N$ 行。在第 $i$ 行，输出第 $i$ 组能够乘坐过山车的时间。

输入格式

$$\begin{aligned} &N \ M \\ &a_1 \ a_2 \ \ldots \ a_N \end{aligned}$$

第一行包含两个整数 $N$ 和 $M$，$N$ 在 $1$ 到 $100,000$ 之间（含），$M$ 在 $1$ 到 $10^9$ 之间（含）。$N$ 表示组的数量，$M$ 表示过山车的容量。

第二行包含 $N$ 个整数，每个整数在 $1$ 到 $M$ 之间（含）。对于每个 $i$（$1 \leq i \leq N$），$a_i$ 表示第 $i$ 组的人数。

输出格式

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

3 5
2 4 1

0
1
1

2 1000000000
1000000000 1000000000

0
1

提示

翻译由 DeepSeek V3.2 完成