Description

When both the sum of the first $K$ elements and the sum of the last $K$ elements are not greater than $S$, we call this sequence of $2\times K$ elements interesting.

You are given a sequence $A$ of length $N$. For each position, output the length of the longest interesting subarray starting at that position.

Input Format

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

The next $N$ lines each contain an integer $A_i$ from the sequence $A$. These integers are positive, and their total sum does not exceed $2\times 10^9$.

Output Format

Output $N$ lines in total. The $i$-th line contains one integer: the length of the longest interesting subarray starting from the $i$-th element.

If there is no interesting subarray starting at the current position, output 0.

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 

Hint

Constraints

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

Notes

The score of this problem follows the original COCI settings, with a full score of $120$.

This problem is translated from COCI2010-2011 CONTEST #5 T5 DVONIZ。

Translated by ChatGPT 5