H. BattleCows 2
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фермер Джон хочет провести еще один турнир с $$$n$$$ коровами, где $$$i$$$-я корова имеет уровень навыка $$$a_i$$$. Следующий процесс повторяется, пока в очереди не останется только одна корова.

  • Первая корова в очереди сражается со второй коровой в очереди, и корова с более высоким уровнем навыка побеждает. Если есть ничья, побеждает первая корова.
  • Уровень навыка победившей коровы устанавливается равным $$$x + y$$$, где $$$x$$$ — уровень навыка победившей коровы, а $$$y$$$ — уровень навыка проигравшей коровы.
  • Проигравшая корова покидает очередь.

Однако, чтобы сохранить точность к настоящему соревнованию USACOW, корова может жульничать до $$$k$$$ раз. Это означает, что даже если она проигрывает матч, фермер Джон будет считать, что проигравшая корова выиграла матч, что означает, что уровень навыка проигравшей коровы будет установлен равным $$$x + y$$$, где $$$x$$$ — уровень навыка победившей коровы, а $$$y$$$ — уровень навыка проигравшей коровы, и победившая корова покинет очередь.

Позиция $$$x$$$ хороша для коровы $$$i$$$, если корова $$$i$$$ может быть удалена из своего первоначального положения и вставлена на индекс $$$x$$$ без изменения порядка других коров и быть единственной коровой, оставшейся в очереди, когда турнир закончится, при условии, что ни одна другая корова не жульничает.

Для каждой коровы в очереди вычислите количество хороших позиций для этой коровы.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \leq k \lt n$$$) — количество коров и количество жульничеств, которые может использовать корова.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — уровни навыка коров.

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

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

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

Пример
Входные данные
7
2 0
2 1
2 0
1 1
3 1
1 1 3
3 0
2 1 1
3 1
1 3 1
4 1
1 2 1 3
7 2
1 3 3 17 39 3 12
Выходные данные
2 0 
1 1 
2 2 3 
2 0 0 
3 3 2 
4 4 4 4 
4 6 6 7 7 5 7
Примечание

Для первого набора входных данных корова $$$2$$$ проиграет, независимо от того, где она будет расположена, а корова $$$1$$$ выиграет, независимо от того, где она будет расположена.

Для второго набора входных данных обе коровы могут выиграть, находясь на позиции $$$1$$$, но не могут на позиции $$$2$$$, что означает, что у каждой из них есть $$$1$$$ хорошая позиция.

Для третьего набора входных данных давайте посмотрим на корову $$$1$$$.

  • Если корова $$$1$$$ будет на позиции $$$1$$$, то она выиграет свой первый матч, сделав ее уровень навыка равным $$$2$$$, и сможет жульничать, чтобы выиграть свой второй матч.
  • Если корова $$$1$$$ будет на позиции $$$2$$$, то ей придется жульничать, чтобы выиграть свой первый матч, но затем она проиграет свой второй матч.
  • Если корова $$$1$$$ будет на позиции $$$3$$$, то ей придется жульничать, чтобы выиграть свой первый матч, и у нее не будет больше матчей.