Sisyphus 被指派去耕作一塊狹長的農田。

這塊農田從左到右被劃分為 $n$ 個格子，編號為 $1$ 到 $n$。起初，所有格子都長滿了雜草，而 Sisyphus 站在第 $1$ 個格子。他會從第 $1$ 個格子走到第 $n$ 個格子，然後再走回第 $1$ 個格子。他檢查並清除所經過的每個格子中的雜草需要 $1$ 小時（無論該格子中是否真的有雜草）。在兩個格子之間移動所需的時間可以忽略不計，因此一輪檢查需要 $(2n - 1)$ 小時，期間前 $(n - 1)$ 個格子會被檢查兩次，而第 $n$ 個格子只會被檢查一次。每一輪檢查結束後，他需要報告清除了多少個格子的雜草，而報告所需的時間也可以忽略不計。

然而，農田底下有源源不絕的雜草種子。在 Sisyphus 清除第 $i$ 個格子的雜草並離開該格子後，雜草會在 $a_i$ 小時又 $1$ 分鐘後重新生長。具體來說，如果 Sisyphus 在雜草重新生長時剛好再次檢查該格子，那麼新長出的雜草也會被清除。

Camus 想要知道，對於每個 $1 \le k \le m$，Sisyphus 在第 $k$ 輪檢查中需要清除多少個格子的雜草。如果 Sisyphus 已經知道這些數字，他應該會感到快樂。

輸入格式

輸入包含多組測試資料。第一行包含一個整數 $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

輸出 1

4 3 4
6 3 4 3
5 3 3

說明

我們在下方說明第一個範例測試資料。空白的格子表示沒有雜草的格子，陰影格子表示有雜草的格子（包含當前正在被清除的雜草），$S$ 表示 Sisyphus，$t$ 表示當前時間（以小時為單位），$cnt$ 表示本輪中已經清除了多少個格子的雜草（包含當前正在被清除的雜草）。