안테나 분석

Åke는 자신이 사는 도시에 수상한 5G 방사선이 있을지도 모른다는 이야기를 들었다. 이를 확인하려고 그는 지붕 위의 안테나로 매일 5G 수치를 측정한다. 하지만 그는 이 데이터를 어떻게 분석해야 할지 모른다.

$n$일 연속의 측정값이 수열 $x_1, \ldots, x_n$으로 주어진다($x_i$는 $i$일째의 측정값). 또한 Åke가 기대하는 일별 방사선 변동의 크기를 나타내는 상수 $c$가 주어진다. 각 날짜 $i$에 대해, 예상 변동을 고려한 뒤 $i$일째 측정값과 그 이전 날짜의 측정값 사이의 가장 큰 차이를 구하려고 한다. 정확히는 $j \le i$일 때 [|x_i-x_j| - c \cdot |i-j|]의 최댓값을 구하는 것이다. 즉, 최근에 일어난 5G 수치의 큰 차이를 찾으려는 것이다.

첫째 줄에 두 정수 $n$과 $c$가 주어진다($1 \le n \le 4 \cdot 10^5$, $1 \le c \le 10^6$). $n$은 측정 횟수, $c$는 기대되는 일별 변동이다. 둘째 줄에 $n$개의 정수 $x_1,x_2,\dots,x_n$이 주어진다($1 \le x_i \le 10^6$, $i=1,2,\dots,n$). 이는 $n$일 동안의 측정값이다.

$n$개의 정수 $y_1, \ldots, y_n$을 출력한다. $y_i$는 $i$일째의 가장 큰 차이이다.