Problem H
Slide Count

In your programming class, you are given an assignment to analyze an integer array using a sliding window algorithm. Specifically, given $N$ integers $w_1, \ldots , w_ N$ and some constant $C$, the sliding window algorithm maintains start and end indices $s$ and $e$ such that

• initially $s = e = 1$;

• as long as $s \leq N$:

  • if $e+1 > N$, then increment $s$;

  • else if $w_ s + \cdots + w_{e+1} > C$, then increment $s$;

  • else increment $e$.

During the execution of this algorithm, each distinct pair of indices $(s,e)$ defines a window. An element $w_ i$ belongs to the window defined by $(s,e)$ if $s \leq i \leq e$. Notice that if $s > e$, the window is empty.

Consider the first sample input below. The windows appearing during the execution of the algorithm are defined by $(1,1)$, $(1,2)$, $(1,3)$, $(2,3)$, $(3,3)$, $(3,4)$, $(4,4)$, $(5,4)$, $(5,5)$, and $(6,5)$.

For each element $w_ i$, determine how many different windows it belongs to during the execution of the sliding window algorithm.

Input

The first line of input contains two integers $N$ ($1 \leq N \leq 100\, 000$), which is the number of elements, and $C$ ($1 \leq C \leq 1\, 000\, 000$), which is the sliding window constant.

The next line contains $N$ integers $w_1, \ldots , w_ N$ ($0 \leq w_ i \leq C$).

Output

For each element, in order, display the number of different windows it belongs to during the execution of the algorithm.

5 3
1 1 1 2 2

3
3
4
2
1 

5 10
1 2 3 4 5

4
4
4
5
2