DVONIZ

문제

We say that a sequence of 2*K 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. 

입력

The first line contains integers N and S (2 ≤ N ≤ 100 000, 1 ≤ S ≤ 2*10⁹). 

The following N lines contain the sequence A, one integer per line. The integers are positive and their sum does not exceed 2*10⁹. 

출력

Output must consist of N lines. 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). 

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