DVONIZ

문제

Author: Goran Žužić

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 ≤ 2109). The following N lines contain the sequence A, one integer per line. The integers are positive and their sum does not exceed 2109.

출력

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

예제 입력 1

5 10000
1
1
1
1
1

예제 출력 1

4
4
2
2
0

예제 입력 2

5 9
1
1
10
1
9

예제 출력 2

2
0
0
2
0

예제 입력 3

8 3
1
1
1
1
1
1
1
1

예제 출력 3

6
6
6
4
4
2
2
0