Problem N
Dvoniz

We say that a sequence of $2K$ elements is interesting if neither the sum of the first $K$ elements, nor the sum of the last $K$ elements, is greater than $S$. A sequence $A$ of length $N$ is given. For every element, output the length of the longest interesting subsequence starting with that element.

Input

The first line contains integers $N$ and $S$ ($2 \leq N \leq 100\, 000$, $1 \leq S \leq 2 \cdot 10^9$ ).

The following $N$ lines contain the sequence $A$, one integer per line. The integers are non-negative and their sum does not exceed $2\cdot 10^9$.

Output

Output $N$ lines. The $i$-th line must contain one integer, the length of the longest interesting subsequence starting with the i-th element. If an interesting subsequence at that position doesn’t exist, output 0 (zero).

5 10000
1
1
1
1
1

4
4
2
2
0

5 9
1
1
10
1
9

2
0
0
2
0

8 3
1
1
1
1
1
1
1
1

6
6
6
4
4
2
2
0