Sisyphus has been appointed to cultivate a long strip of farmland.

The farmland is divided into $n$ cells from left to right, numbered from 1 to $n$. At the beginning, all cells are overgrown with weeds, and Sisyphus stands at cell 1. He will walk from cell 1 to cell $n$, and then walk back to cell 1. It takes him 1 hour to check and remove the weeds he finds in each cell he passes (regardless of whether there are actually weeds in that cell). The time taken to move between two cells is negligible, so one round of checking takes him $(2n - 1)$ hours, during which each of the first $(n - 1)$ cells will be checked twice and the $n$-th cell will only be checked once. After each round of checking, he needs to report how many cells of weeds have been removed, and the time taken for the report is also negligible.

However, under the farmland lies an endless supply of weed seeds. After Sisyphus removes the weeds in cell $i$ and leaves that cell, the weeds will regrow after $a_i$ hours and 1 minute. Specifically, if Sisyphus happens to be checking that cell again when the weeds regrow, the newly grown weeds will also be removed.

Camus wants to know, for each $1 \le k \le m$, how many cells of weeds Sisyphus needs to remove during his $k$-th round of checking. If Sisyphus already knows the numbers, he should be happy.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 2 \times 10^3$) indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$), indicating the number of cells and the number of rounds.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$). The weeds in the $i$-th cell will regrow after $a_i$ hours and 1 minute.

It’s guaranteed that neither the sum of $n$ nor the sum of $m$ of all test cases will exceed $10^6$.

Output

For each test case output one line containing $m$ integers separated by a space, where the $i$-th integer indicates how many cells of weeds will be removed during the $i$-th round of checking.

Examples

Input 1

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

Output 1

4 3 4
6 3 4 3
5 3 3

Note

We illustrate the first sample test case below. The empty cells indicate the cells without weeds, the shaded cells indicate the cells with weeds (including the weeds currently being removed), S indicates Sisyphus, t indicates the current time in hours, and cnt indicates how many cells of weeds have been removed in this round (including the weeds currently being removed).