Syzyf został wyznaczony do uprawy długiego pasa ziemi uprawnej.

Ziemia jest podzielona na $n$ pól od lewej do prawej, ponumerowanych od 1 do $n$. Na początku wszystkie pola są zarośnięte chwastami, a Syzyf stoi przy polu 1. Będzie on szedł od pola 1 do pola $n$, a następnie wróci do pola 1. Sprawdzenie i usunięcie chwastów, które znajdzie na każdym mijanym polu, zajmuje mu 1 godzinę (niezależnie od tego, czy na danym polu faktycznie są chwasty). Czas potrzebny na przemieszczenie się między dwoma polami jest pomijalny, więc jedna runda sprawdzania zajmuje mu $(2n - 1)$ godzin, podczas których każde z pierwszych $(n - 1)$ pól zostanie sprawdzone dwukrotnie, a $n$-te pole zostanie sprawdzone tylko raz. Po każdej rundzie sprawdzania musi on zgłosić, ile pól z chwastami zostało oczyszczonych, a czas potrzebny na raport jest również pomijalny.

Jednak pod ziemią uprawną znajduje się nieskończony zapas nasion chwastów. Po tym, jak Syzyf usunie chwasty na polu $i$ i opuści to pole, chwasty odrosną po $a_i$ godzinach i 1 minucie. W szczególności, jeśli Syzyf akurat sprawdza to pole ponownie w momencie, gdy chwasty odrastają, nowo wyrosłe chwasty również zostaną usunięte.

Camus chce wiedzieć, dla każdego $1 \le k \le m$, ile pól z chwastami Syzyf musi oczyścić podczas swojej $k$-tej rundy sprawdzania. Jeśli Syzyf zna już te liczby, powinien być szczęśliwy.

Wejście

Dostępnych jest wiele zestawów danych testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 2 \times 10^3$), określającą liczbę zestawów danych. Dla każdego zestawu danych:

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n, m \le 10^6$), określające liczbę pól oraz liczbę rund.

Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$). Chwasty na $i$-tym polu odrosną po $a_i$ godzinach i 1 minucie.

Gwarantuje się, że suma $n$ oraz suma $m$ dla wszystkich zestawów danych nie przekraczają $10^6$.

Wyjście

Dla każdego zestawu danych wypisz jedną linię zawierającą $m$ liczb całkowitych oddzielonych spacją, gdzie $i$-ta liczba oznacza, ile pól z chwastami zostanie oczyszczonych podczas $i$-tej rundy sprawdzania.

Przykład

Wejście 1

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

Wyjście 1

4 3 4
6 3 4 3
5 3 3

Uwagi

Poniżej ilustrujemy pierwszy przykładowy zestaw danych. Puste pola oznaczają pola bez chwastów, zacienione pola oznaczają pola z chwastami (w tym chwasty aktualnie usuwane), S oznacza Syzyfa, $t$ oznacza aktualny czas w godzinach, a $cnt$ oznacza, ile pól z chwastami zostało usuniętych w tej rundzie (w tym chwasty aktualnie usuwane).