这个问题由 Ema 提出。

给定一个包含 $n$ 个数字的数组 $N$ 和一个整数 $k$，你的任务是将 $N$ 分割成 $k$ 个非空的连续部分，使得任意部分的和的最大值最小。输出这 $k$ 个部分的长度。如果存在多种方案，输出字典序最大的方案。

如果存在一个整数 $i(1 \le i \le n)$，使得方案 A 和方案 B 的前 $i-1$ 个部分的长度相同，且方案 A 的第 $i$ 个部分比方案 B 的第 $i$ 个部分长，则称方案 A 的字典序大于方案 B。

例如，给定 $N = [5, 1, 0, 2, 7, -3, 4]$ 和 $k = 3$，你应该输出 $3, 3, 1$，因为最优分割为 $[5, 1, 0], [2, 7, -3], [4]$。注意，此示例仅为方便说明，你的程序应遵循下述格式。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 3 \times 10^5$)，分别表示数组的长度和分割的份数。

下一行包含 $n$ 个整数 $N = [a_1, a_2, \dots, a_n]$ ($|a_i| \le 10^9$)，表示该数组。

保证所有测试数据的 $n$ 之和不超过 $6 \times 10^5$。

输出格式

对于每组测试数据，输出一行，包含 $k$ 个整数，表示这 $k$ 个部分的长度。再次提醒，你的答案必须是字典序最大的方案。

样例

样例输入 1

3
7 3
5 1 0 2 7 -3 4
6 4
-1 3 -2 4 -3 5
6 2
0 -2 0 -1 -1 0

样例输出 1

3 3 1
1 1 2 2
3 3