西西弗斯被指派去耕种一片长条形的农田。

农田被从左到右划分为 $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

样例输出 1

4 3 4
6 3 4 3
5 3 3

说明

我们在下方展示了第一个样例测试数据。空白单元格表示没有杂草的单元格，阴影单元格表示有杂草的单元格（包括当前正在被清除的杂草），$S$ 表示西西弗斯，$t$ 表示当前时间（以小时为单位），$cnt$ 表示本轮中已经清除了多少个单元格的杂草（包括当前正在被清除的杂草）。