60002 허수아비 Gold III

문제

수직선의 위치 0에서 오른쪽 방향으로 힘 P를 가진 화살이 발사된다. 각 정수 위치 i (1 ≤ i ≤ N)에는 방어력 A_i를 가진 허수아비를 최대 하나 설치할 수 있다.

화살이 허수아비에 부딪치면, 화살의 힘이 방어력 이하일 경우 즉시 멈춘다. 화살의 힘이 방어력보다 크면, 힘이 A_i만큼 줄어든 채 계속 진행한다.

f(i)를 “화살이 위치 i에서 멈추거나 위치 i보다 왼쪽에서 멈추도록 하기 위해 필요한 허수아비의 최소 개수”로 정의한다. 화살을 멈추게 할 수 없으면 -1이다.

f(1), f(2), …, f(N)을 구하시오.

입력

첫째 줄에 정수 N과 화살의 힘 P가 주어진다. (1 ≤ N ≤ 500,000, 1 ≤ P ≤ 10^9)

둘째 줄에 N개의 정수 A_1, A_2, …, A_N이 주어진다. (1 ≤ A_i ≤ 10^9)

출력

f(1), f(2), …, f(N)의 값을 공백으로 구분하여 출력한다.

5 10
3 6 1 1 10

-1 -1 3 3 1

3 10
20 20 20

1 1 1

1 5
3

-1