CF2258B2 Carrot Chopdown (Hard Version)

这是本题的高难度版本。不同之处在于，在本题中，你需要对不同的 $k$ 值分别解决问题。只有当你解决了本题的所有版本，才能 hack 本题。 Alp 喜欢吃胡萝卜。这天他还没吃午饭，想买一份胡萝卜沙拉带去外面吃。不过他有一个奇怪的执念：所有胡萝卜必须长度完全相同，否则他觉得沙拉不好看。由于他此刻正在街上，自己手头又没有刀子，无法自己切胡萝卜。他需要你用机器把胡萝卜切好，然后再卖给他。 你有 $n$ 根美味的胡萝卜，长度分别为 $a_1,a_2,\ldots,a_n$。你还拥有一台切割机器，其工作方式如下： - 每次操作时，你可以任选一组胡萝卜（无论是否已被切过都可以再次选择），并选择一个正整数 $x$（每次操作选的 $x$ 可以不同）。 - 对于每根被选中的胡萝卜，设长度为 $l$。如果 $l\leq x$，则这根胡萝卜不变；否则，将其切分为两根胡萝卜，长度分别为 $x$ 和 $l-x$。 我们最终会把部分切好的胡萝卜卖给那位有趣的顾客，要求这些胡萝卜长度全部相同。 你的任务是：经过恰好 $k$ 次机器操作后，最多能卖出几根长度完全相同的胡萝卜？对于每个 $k=1,2,\ldots,m$，都要分别计算答案。

每个测试点包含多组测试数据。第一行输入测试组数 $t$（$1\leq t\leq10^4$）。每组数据包含： 第一行有 $n$ 和 $m$（$1\leq n,m\leq 2\times10^5$），分别表示胡萝卜数量和胡萝卜最大长度。 第二行有 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\leq a_i\leq m$），表示初始每根胡萝卜的长度。 保证所有测试组 $n$ 之和不超过 $2\times10^5$，所有测试组 $m$ 之和也不超过 $2\times10^5$。

对每组测试数据，输出 $m$ 个整数，依次表示 $k=1,2,\dots,m$ 时的答案。

在第一个测试点中，给定的胡萝卜为 $[1,2,3,4,4]$。 对于 $k=1$，最优方案是选择 $x=2$，选中 $[2,3,4,4]$。操作后得到 $[1,2,2,1,2,2,2,2]$。能卖出 $6$ 根长度为 $2$ 的胡萝卜。 对于 $k=2$，仍然先以 $x=2$ 切 $[2,3,4,4]$，得到 $[1,2,2,1,2,2,2,2]$。第二步对全部胡萝卜选择 $x=1$，结果得到 $14$ 根长度为 $1$ 的胡萝卜。此时最多可以卖出 $14$ 根长度为 $1$ 的胡萝卜。 由 ChatGPT 5 翻译