Problem Background

The problem statement is identical to the original problem P7635 [COCI2010-2011#5] DVONIZ, except for the data range, time and space limits, and the score.

Problem Description

A sequence of $2 \times K$ elements is considered interesting if the sum of the current $K$ elements or the sum of the last $K$ elements does not exceed $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 following $N$ lines each contain an integer $A_i$ from the sequence $A$. All integers are positive and their sum does not exceed $2 \times 10^9$.

Output Format

Output consists of $N$ lines. The $i$-th line contains an integer representing the length of the longest interesting subsequence starting from the $i$-th element.

If there is no interesting subsequence starting at 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

[Sample Explanation #1]

For the first position in Sample 1, there are 4 subsequences, all of which meet the conditions, so the longest subsequence of length 4 is taken.

[Data Range]

For 30% of the data, $2 \le N \le 200$.

For 50% of the data, $2 \le N \le 5 \times 10^3$.

For 70% of the data, $2 \le N \le 2 \times 10^5$.

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

见题面 Input 部分

见题面 Output 部分