Slide Count

문제

In your programming class, you are given an assignment to analyze an integer array using a sliding window algorithm.  Specifically, given $NN$ integers $w_1,\dots ,w_{N}w\_1,\; \backslash ldots,\; w\_N$ and some constant $CC$, the sliding window algorithm maintains start and end indices $ss$ and $ee$ such that

• initially $s=e=1s\; =\; e\; =\; 1$;
• as long as $s\le Ns\; \backslash leq\; N$:
  • if $e+1>Ne+1\; >\; N$, then increment $ss$;
  • else if $w_s+\cdots +w_{e+1}>Cw\_s\; +\; \backslash cdots\; +\; w\_\{e+1\}\; >\; C$, then increment $ss$;
  • else increment $ee$.

During the execution of this algorithm, each distinct pair of indices $(s,e)(s,e)$ defines a window.  An element $w_{i}w\_i$ belongs to the window defined by $(s,e)(s,e)$ if $s\le i\le es\; \backslash leq\; i\; \backslash leq\; e$.  Notice that if $s>es\; >\; 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,1)$, $(1,2)(1,2)$, $(1,3)(1,3)$, $(2,3)(2,3)$, $(3,3)(3,3)$, $(3,4)(3,4)$, $(4,4)(4,4)$, $(5,4)(5,4)$, $(5,5)(5,5)$, and $(6,5)(6,5)$.

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

입력

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

The next line contains $NN$ integers $w_1,\dots ,w_{N}w\_1,\; \backslash ldots,\; w\_N$ ($0\le w_i\le C0\; \backslash leq\; w\_i\; \backslash leq\; C$).

출력

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