Problem M
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,\dots ,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\le 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\le i\le 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\le N\le 100000$), which is the number of elements, and $C$ ($1\le C\le 1000000$), which is the sliding window constant.

The next line contains $N$ integers $w_1,\dots ,w_N$ ($0\le w_i\le 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