Åke 听说他所在的城市可能存在可疑的 5G 辐射。为了进行测试，他使用屋顶的天线每天测量 5G 水平。然而，他不知道该如何分析这些数据。

我们得到了连续 $n$ 天的测量值列表 $x_1, \dots, x_n$（其中 $x_i$ 表示第 $i$ 天的测量值），以及一个常数 $c$，用于衡量 Åke 预期的每日辐射变化量。我们希望对于每一天 $i$，在考虑了预期变化后，找出第 $i$ 天的测量值与之前任何一天测量值之间最显著的差异。更准确地说，目标是找到以下表达式的最大值：

$$|x_i - x_j| - c \cdot |i - j|$$

其中 $j \le i$。也就是说，我们想要找到最近发生的 5G 水平的较大差异。

输入格式

第一行包含两个整数 $n$ 和 $c$ ($1 \le n \le 4 \cdot 10^5$, $1 \le c \le 10^6$)，分别表示测量天数和预期的每日变化量。第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$ ($1 \le x_i \le 10^6$，对于 $i = 1, 2, \dots, n$)，给出了 $n$ 天的测量值。

输出格式

输出 $n$ 个整数 $y_1, \dots, y_n$，其中 $y_i$ 是第 $i$ 天最显著的差异。

样例

样例输入 1

5 1
2 7 1 5 4

样例输出 1

0 4 5 3 1