题目描述

这是该问题的困难版本。与简单版本不同的是，你需要分别求解 $k = 1, 2, \dots, m$ 时的答案。

你有 $n$ 根胡萝卜，它们的初始长度分别为 $a_1, a_2, \dots, a_n$。为了把这些胡萝卜卖给一个只想要长度完全相同的胡萝卜的顾客，你需要使用一台切菜机对胡萝卜进行处理。

切菜机的工作规则如下：

• 在每次操作中，你可以选择任意一个胡萝卜的集合（切开后的胡萝卜也可以再次被选择）以及一个正整数 $x$（每次操作选定的 $x$ 可以不同）。
• 接着，对于被选中的每一根胡萝卜（设其当前长度为 $l$）：
  • 如果 $l \le x$，该胡萝卜保持不变；
  • 如果 $l > x$，该胡萝卜将被切分为两根长度分别为 $x$ 和 $l-x$ 的胡萝卜。

请问对于每个 $k \in \{1, 2, \dots, m\}$，如果恰好使用切菜机 $k$ 次，你最多能得到多少根长度完全相同的胡萝卜？请对每个 $k$ 独立求解。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

对于每个测试用例：

• 第一行包含两个正整数 $n$ 和 $m$（$1 \le n, m \le 2 \times 10^5$）—— 分别表示胡萝卜的数量以及需要求解的最大操作次数 $m$（同时也是胡萝卜的最大可能长度）。
• 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le m$）—— 表示每根胡萝卜的初始长度。

输出格式

对于每个测试用例，输出一行 $m$ 个整数，相邻整数之间用一个空格隔开，依次表示当 $k = 1, 2, \dots, m$ 时，能得到的具有相同长度的胡萝卜的最大数量。

样例输入 1

6
5 4
1 2 3 4 4
5 8
1 1 8 8 8
1 8
6
7 9
1 7 5 1 7 5 3
4 1
1 1 1 1
3 5
3 1 5

样例输出 1

6 14 14 14
6 12 26 26 26 26 26 26
2 3 6 6 6 6 6 6
7 17 29 29 29 29 29 29 29
4
3 7 9 9 9

说明

样例解释

在第一个测试用例中，给定的胡萝卜长度为 $[1, 2, 3, 4, 4]$。

• 当 $k=1$ 时，最优的选择是取 $x=2$，并选择胡萝卜集合 $[2, 3, 4, 4]$ 进行操作。操作完成后，所有的胡萝卜长度变为 $[1, 2, 2, 1, 2, 2, 2, 2]$。此时我们总共拥有 $6$ 根长度为 $2$ 的胡萝卜，因此答案为 $6$。
• 当 $k=2$ 时，第一步操作同上，取 $x=2$ 并选择集合 $[2, 3, 4, 4]$，得到 $[1, 2, 2, 1, 2, 2, 2, 2]$。第二步操作取 $x=1$ 并选择所有现有的胡萝卜。这会把所有长度为 $2$ 的胡萝卜全部切成两根长度为 $1$ 的胡萝卜。最终会得到 $14$ 根长度均为 $1$ 的胡萝卜，因此答案为 $14$。

数据范围

• 对于所有测试点，保证 $1 \le t \le 10^4$。
• 对于每个测试用例，保证 $1 \le n, m \le 2 \times 10^5$。
• 对于每个测试用例，保证 $1 \le a_i \le m$。
• 保证同一测试点内所有测试用例的 $n$ 之和不超过 $2 \times 10^5$，所有测试用例的 $m$ 之和也不超过 $2 \times 10^5$。
• 保证所有的输入数值均为整数。