OpenKattis
Kattis Set 12

Start

2019-04-08 13:00 UTC

Kattis Set 12

End

2019-04-15 09:29 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -219 days 0:13:31

164:29:59

0:00:00

Problem GDvoniz

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).

Sample Input 1 Sample Output 1
5 10000
1
1
1
1
1

4
4
2
2
0

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

2
0
0
2
0

Sample Input 3 Sample Output 3
8 3
1
1
1
1
1
1
1
1

6
6
6
4
4
2
2
0