在编程课上，你接到了一项任务，要求使用滑动窗口算法分析一个整数数组。具体来说，给定 $N$ 个整数 $w_1, \dots, w_N$ 和一个常数 $C$，滑动窗口算法维护起始索引 $s$ 和结束索引 $e$，使得：

• 初始时 $s = e = 1$；
• 只要 $s \le N$：
  • 如果 $e + 1 > N$，则增加 $s$；
  • 否则，如果 $w_s + \dots + w_{e+1} > C$，则增加 $s$；
  • 否则，增加 $e$。

在该算法的执行过程中，每一对不同的索引 $(s, e)$ 定义了一个窗口。如果 $s \le i \le e$，则元素 $w_i$ 属于由 $(s, e)$ 定义的窗口。注意，如果 $s > e$，则窗口为空。

考虑下方的第一个样例输入。算法执行过程中出现的窗口定义为 $(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4), (4, 4), (5, 4), (5, 5)$ 和 $(6, 5)$。

对于每个元素 $w_i$，确定它在滑动窗口算法执行过程中所属的不同窗口的数量。

输入格式

第一行包含两个整数 $N$ ($1 \le N \le 100\,000$)，即元素个数，以及 $C$ ($1 \le C \le 1\,000\,000$)，即滑动窗口常数。

下一行包含 $N$ 个整数 $w_1, \dots, w_N$ ($0 \le w_i \le C$)。

输出格式

按顺序输出每个元素在算法执行过程中所属的不同窗口的数量。

样例

样例输入 1

5 3
1 1 1 2 2

样例输出 1

3
3
4
2
1

样例输入 2

5 10
1 2 3 4 5

样例输出 2

4
4
4
5
2