Problem Description

A sequence of $2 \times K$ elements is considered interesting if the sum of the first $K$ elements and the sum of the last $K$ elements are both not greater than $S$.

Given a sequence $A$ of length $N$, for each element, output the length of the longest interesting subsequence starting from that element.

Input Format

The first line contains two integers, $N$ and $S$.

The next $N$ lines each contain a single integer from the sequence $A$. All integers are positive and their sum does not exceed $2 \times 10^9$.

Output Format

Output $N$ lines. The $i$-th line should contain a single integer, the length of the longest interesting subsequence starting from the $i$-th element.

If there is no interesting subsequence starting from the current position, output 0.

Sample Input and Output

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

Sample Input #3

8 3
1
1
1
1
1
1
1
1

Sample Output #3

6
6
6
4
4
2
2
0

Notes

[Data Range]

For $100\%$ of the data, $2 \le N \le 10^5$, $1 \le S \le 2 \times 10^9$.

[Explanation]

This problem is scored according to the original COCI settings, with a full score of $120$.

The problem is translated from COCI2010-2011 CONTEST #5 T5 DVONIZ.

见题面 Input 部分

见题面 Output 部分