G. Убрали индекс
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив $$$b_1, b_2, \ldots, b_m$$$ называется хорошим, если для каждого $$$i$$$ $$$(1 \leq i \lt m)$$$ выполнено $$$b_{i+1} \geq b_i$$$ и $$$b_{i+1} - b_i \leq k$$$. Массив длины $$$1$$$ всегда является хорошим.

Вам дан изначально хороший массив $$$a_1, a_2, \ldots, a_n$$$. Решите следующую задачу для каждого $$$i$$$ $$$(1 \leq i \leq n)$$$ независимо:

  • $$$i$$$-й элемент массива $$$a$$$ удаляется, и получается $$$a = [a_1, a_2, \ldots, a_{i-1}, a_{i+1}, \ldots, a_n]$$$. За одну операцию вы можете вычесть $$$1$$$ из любого элемента массива $$$a$$$. Каково минимальное количество операций, необходимое, чтобы снова сделать массив $$$a$$$ хорошим?
Входные данные

Первая строка каждого набора входных данных содержит $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$). Гарантируется, что массив $$$a$$$ изначально хороший.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел, разделённых пробелами, в одной строке: $$$i$$$-е число должно обозначать ответ для $$$i$$$-го индекса.

Пример
Входные данные
7
4 2
1 2 4 5
4 1
1 2 3 4
5 7
1 8 9 16 20
5 1000000000
1 6 7 67 6767
6 1
1 1 2 2 3 4
4 1
1 2 3 3
4 2
1 2 4 6
Выходные данные
0 1 1 0 
0 2 1 0 
0 2 1 4 0 
0 0 0 0 0 
0 0 0 0 1 0 
0 1 0 0 
0 2 2 0
Примечание

В первом наборе входных данных:

  • $$$i = 1$$$, $$$a = [2, 4, 5]$$$. Так как массив $$$a$$$ по-прежнему хороший, нам не нужно выполнять никаких операций.
  • $$$i = 2$$$, $$$a = [1, 4, 5]$$$. Если выполнить операцию один раз над $$$2$$$-м элементом, получится $$$a = [1, 3, 5]$$$, что является хорошим массивом.
  • $$$i = 3$$$, $$$a = [1, 2, 5]$$$. Если выполнить операцию один раз над $$$3$$$-м элементом, получится $$$a = [1, 2, 4]$$$, что является хорошим массивом.
  • $$$i = 4$$$, $$$a = [1, 2, 4]$$$. Так как массив $$$a$$$ по-прежнему хороший, нам не нужно выполнять никаких операций.

В четвёртом наборе входных данных массив $$$a$$$ останется хорошим независимо от того, какой элемент мы удалим, поэтому ответ для каждого индекса равен $$$0$$$.