#1797 흥미로운 수열

2 s   128 MB  

Description

우리는 2*K개의 원소로 이뤄진 수열에 대하여 앞의 K개의 원소 합과, 뒤의 K개의 원소 합이 모두 S보다 크지 않을 때, 이를 흥미로운 수열이라 한다. 길이 N인 수열 A가 주어졌을 때, 모든 원소마다 자기 자신으로 시작하는 가장 긴 흥미로운 수열의 길이를 출력한다. 여기서 흥미로운 수열은 수열 A의 연속된 부분수열이다.

Input

첫 번째 줄에는 N(2≤N≤100,000)과 S(1≤S≤2 * 109)가 입력된다.

두 번째 줄부터 N개의 줄에 걸쳐 수열 A의 원소가 한줄에 하나씩 입력된다. 모두 양수이며 그 합은 2*109을 초과하지 않는다.

Output

출력은 N개의 줄로 이뤄지며, i번째 줄에는 수열 A의 i번째 원소로 시작되는 흥미로운 수열의 최대 길이를 출력한다. 만약 흥미로운 수열이 존재하지 않으면 0을 출력한다.

Sample Input

Sample Output

5 10000
1
1
1
1
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