Сизиф был назначен возделывать длинную полосу сельскохозяйственных угодий.

Угодья разделены на $n$ ячеек слева направо, пронумерованных от $1$ до $n$. В начале все ячейки заросли сорняками, а Сизиф стоит у ячейки $1$. Он будет идти от ячейки $1$ до ячейки $n$, а затем вернется обратно к ячейке $1$. У него уходит $1$ час на проверку и удаление сорняков, которые он находит в каждой ячейке, мимо которой проходит (независимо от того, есть ли на самом деле сорняки в этой ячейке). Время, затрачиваемое на перемещение между двумя ячейками, пренебрежимо мало, поэтому один раунд проверки занимает у него $(2n - 1)$ часов, в течение которых каждая из первых $(n - 1)$ ячеек будет проверена дважды, а $n$-я ячейка будет проверена только один раз. После каждого раунда проверки ему нужно отчитаться о том, сколько ячеек с сорняками было очищено, и время, затраченное на отчет, также пренебрежимо мало.

Однако под землей находится бесконечный запас семян сорняков. После того как Сизиф удаляет сорняки в ячейке $i$ и покидает эту ячейку, сорняки отрастают через $a_i$ часов и $1$ минуту. В частности, если Сизиф снова проверяет эту ячейку в момент, когда сорняки отрастают, вновь выросшие сорняки также будут удалены.

Камю хочет знать для каждого $1 \le k \le m$, сколько ячеек с сорняками Сизифу нужно удалить во время его $k$-го раунда проверки. Если Сизиф уже знает эти числа, он должен быть счастлив.

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

Имеется несколько тестовых случаев. Первая строка входных данных содержит целое число $T$ ($1 \le T \le 2 \times 10^3$), указывающее количество тестовых случаев. Для каждого тестового случая:

Первая строка содержит два целых числа $n$ и $m$ ($1 \le n, m \le 10^6$), указывающие количество ячеек и количество раундов.

Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$). Сорняки в $i$-й ячейке отрастают через $a_i$ часов и $1$ минуту.

Гарантируется, что ни сумма $n$, ни сумма $m$ по всем тестовым случаям не превышает $10^6$.

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

Для каждого тестового случая выведите одну строку, содержащую $m$ целых чисел, разделенных пробелом, где $i$-е целое число указывает, сколько ячеек с сорняками будет удалено во время $i$-го раунда проверки.

Примеры

Пример 1

3
3 3
0 7 1
5 4
6 16 10 5 10
3 3
2 1 20

4 3 4
6 3 4 3
5 3 3

Примечание

Мы иллюстрируем первый пример ниже. Пустые ячейки обозначают ячейки без сорняков, заштрихованные ячейки обозначают ячейки с сорняками (включая сорняки, которые удаляются в данный момент), $S$ обозначает Сизифа, $t$ обозначает текущее время в часах, а $cnt$ обозначает, сколько ячеек с сорняками было удалено в этом раунде (включая сорняки, которые удаляются в данный момент).