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 100000$, $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).

-----Examples-----
Sample Input 1:
5 10000
1
1
1
1
1
Sample Output 1:
4
4
2
2
0

Sample Input 2:
5 9
1
1
10
1
9
Sample Output 2:
2
0
0
2
0

见题面

见题面