허수아비

문제

수직선의 위치 $00$에서 오른쪽 방향으로 힘 $PP$를 가진 화살이 발사된다. 각 정수 위치 $ii$ (1 ≤ i ≤ N)에는 방어력 $A_{i}A\_i$를 가진 허수아비를 최대 하나 설치할 수 있다. 화살이 허수아비에 부딪치면, 화살의 힘이 방어력보다 작거나 같을 경우 화살은 즉시 멈춘다. 반대로 화살의 힘이 방어력보다 크면, 화살의 힘은 현재 화살의 힘에서 $A_{i}A\_i$만큼 줄어든 채 계속 진행한다.

정수 $ii$에 대하여 $f(i)f(i)$의 값을 "화살이 위치 $ii$에서 멈추거나 위치 $ii$보다 왼쪽에서 멈추도록 하기 위해 필요한 허수아비의 최소 개수" 라고 정의하자. 화살을 멈추게 할 수 있는 방법이 없을 때의 값은 −1이다.

예를 들어서 $N=5N\; =\; 5$, $P=10P\; =\; 10$이고 $A_1=3A\_1\; =\; 3$, $A_2=6A\_2\; =\; 6$, $A_3=1A\_3\; =\; 1$, $A_4=1A\_4\; =\; 1$, $A_5=10A\_5\; =\; 10$이라고 하자. 모든 $f(i)f(i)$의 값과 설치한 허수아비의 위치는 다음과 같다.

$ii$	$f(i)f(i)$의 값	설치한 허수아비의 위치
$i=1i\; =\; 1$	$-1-1$	불가능
$i=2i\; =\; 2$	$-1-1$	불가능
$i=3i\; =\; 3$	$33$	$[1,2,3][1,\; 2,\; 3]$
$i=4i\; =\; 4$	$33$	$[1,2,3][1,\; 2,\; 3]$ 혹은 $[1,2,4][1,\; 2,\; 4]$ 중 하나 선택 가능
$i=5i\; =\; 5$	$11$	$[5][5]$

1 ≤ i ≤ N인 모든 $ii$에 대하여 $f(i)f(i)$의 값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 정수 $NN$과 화살의 힘 $PP$가 공백을 사이에 두고 주어진다.

두 번째 줄에 $NN$개의 정수 $A_1,A_2,\cdots ,A_{N}A\_1\; ,\; A\_2\; ,\backslash cdots,\; A\_N$이 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에 $f(1),f(2),\cdots ,f(N)f(1),\; f(2),\; \backslash cdots\; ,\; 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