첫 k 개의 합 과 마지막 k 개의 합이 S 을 넘지 않는다면 2*k 원소들의 나열을 재미있는 수열이라고 한다.

크기 N 인 수열 A 가 주어질 때 모든 원소에 대해 가장 긴 재미있는 수열의 크기를 출력한다.

입력

• 첫 줄에는 정수 N 과 S 가 주어진다.(2 ≤ N ≤ 100 000, 1 ≤ S ≤ 2*10^9).
• 다음 N 라인은 수열 A 가 한 줄에 하나의 정수로 주어진다. 각 수는 음이 아닌 정수이고 합은 2*10^9 을 넘지 않는다.

출력

i 번째 줄은 i 번째 원소로 시작하는 가장 긴 재미있는 부분수열의 크기를 나타내는 정수를 출력한다. 재미있는 수열이 존재하지 않으면 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

입출력 보충

8 3
1
1
1
1
1
1
1
1

• 1 항에서 6 개 1 + 1 + 1 1 + 1 + 1
  
• 2 항에서 6 개 1 + 1 + 1 1 + 1 + 1
  
• 3 항에서 6 개 1 + 1 1 + 1
• 4 항에서 4 개 1 + 1 1 + 1
• 5 항에서 4 개 1 + 1 1 + 1
• 6 항에서 2 개 1 1
• 7 항에서 2 개 1 1
• 8 항에서는 짝수개를 만들수 없어 0 개

출처:coci 2011