B2. Нарезка моркови (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии вам нужно решить задачу для различных значений $$$k$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Алп любит морковь. Поскольку он ещё не обедал, он хочет купить морковный салат, чтобы поесть на улице. Однако у него есть странная навязчивая идея: все морковки должны быть в точности одинаковой длины, иначе салат кажется ему неэстетичным. Так как Алп находится посреди улицы и у него нет ножа, он не может нарезать морковь самостоятельно. Вам нужно разделить все морковки с помощью своей машины и продать их Алпу.

Вам даны $$$n$$$ вкусных морковок размером $$$a_1, a_2, \ldots, a_n$$$. Также вам дана машина для нарезки, которая работает следующим образом.

  • Каждый раз вы выбираете множество морковок (можно выбирать уже нарезанные морковки) и положительное целое число $$$x$$$ (не обязательно одинаковое для каждой операции).
  • После этого рассмотрим каждую выбранную морковку, пусть ее длина равна $$$l$$$. Если $$$l \le x$$$, эта морковка не изменяется, иначе она разделяется на две морковки размером $$$x$$$ и $$$l-x$$$.

Мы хотим продать часть финальных морковок заинтересованному покупателю, который хочет, чтобы все они были одинаковой длины.

Определите максимальное количество морковок, которое мы можем продать ровно после $$$k$$$ использований машины. Решите задачу для каждого $$$k = 1, 2, \ldots, m$$$ независимо.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных содержатся $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) — количество морковок и максимально возможная длина морковки соответственно.

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — исходные размеры морковок.

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

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

Для каждого набора входных данных выведите $$$m$$$ целых чисел — ответ для каждого $$$k=1, 2, \ldots, m$$$.

Пример
Входные данные
6
5 4
1 2 3 4 4
5 8
1 1 8 8 8
1 8
6
7 9
1 7 5 1 7 5 3
4 1
1 1 1 1
3 5
3 1 5
Выходные данные
6 14 14 14
6 12 26 26 26 26 26 26
2 3 6 6 6 6 6 6
7 17 29 29 29 29 29 29 29
4
3 7 9 9 9
Примечание

В первом наборе входных данных даны морковки $$$[1, 2, 3, 4, 4]$$$.

Для $$$k=1$$$ оптимально выбрать $$$x=2$$$ и множество $$$[2, 3, 4, 4]$$$. Мы получим $$$[1, 2, 2, 1, 2, 2, 2, 2]$$$. Можно продать $$$6$$$ морковок длины $$$2$$$.

Для $$$k=2$$$ сначала оптимально выбрать $$$x=2$$$ и множество $$$[2, 3, 4, 4]$$$. Мы получим $$$[1, 2, 2, 1, 2, 2, 2, 2]$$$. Для второй операции оптимально выбрать $$$x=1$$$ и множество всех морковок. Мы получим $$$14$$$ морковок одинаковой длины. Можно продать $$$14$$$ морковок длины $$$1$$$.