CF2258B2.Carrot Chopdown (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, you need to solve the problem for different values of $k$. You can hack only if you solved all versions of this problem.

Alp loves carrots. Since he hasn't eaten lunch yet, he wants to buy a carrot salad to eat outside. However, he has a weird obsession: all the carrots must be the exact same length; otherwise, the salad doesn't look aesthetically pleasing to him. Since he is in the middle of the street and doesn't have a knife, he can't cut the carrots himself. You need to divide all the carrots using your machine and sell them to Alp.

You are given $n$ delicious carrots with sizes $a_1, a_2, \ldots, a_n$. You are also given a cutting machine, which works as follows.

• For each operation, you choose a set of carrots (you can choose chopped carrots again) and a positive integer $x$ (not necessarily the same for each operation).
• After that, consider every chosen carrot, let its length be $l$. If $l \le x$, this carrot is unaffected; otherwise, it is divided into two carrots of sizes $x$ and $l-x$.

We'll sell some of the final carrots to an interesting guy who wants them all to be the same length.

We are asking you to determine the maximum number of carrots we can sell after using this machine exactly $k$ times. Solve the problem for each $k = 1, 2, \ldots, m$ independently.

这是该问题的困难版本。两个版本的区别在于，在本版本中，你需要对不同的 $k$ 值求解该问题。仅当你已解决该问题的所有版本时，才允许你进行 hack。

阿尔普热爱胡萝卜。由于他尚未吃午餐，他想买一份胡萝卜沙拉，到户外享用。然而，他有一种奇特的执念：所有胡萝卜的长度必须完全相同；否则，这盘沙拉在他看来便缺乏美学上的吸引力。由于他正身处街道中央，且身边没有刀具，因此他无法自行切割胡萝卜。你需要使用你的切割机器将所有胡萝卜进行分割，再出售给阿尔普。

你被给定 $n$ 根美味的胡萝卜，其长度分别为 $a_1, a_2, \ldots, a_n$。你还拥有一台切割机器，其工作方式如下：

• 每次操作中，你选择一组胡萝卜（可重复选择已被切过的胡萝卜）以及一个正整数 $x$（每次操作的 $x$ 值不一定相同）；
• 接着，对每个被选中的胡萝卜，设其当前长度为 $l$：若 $l \le x$，则该胡萝卜保持不变；否则，它将被切成两根长度分别为 $x$ 和 $l - x$ 的胡萝卜。

我们将把最终得到的部分胡萝卜出售给一位特别的顾客，他要求所购胡萝卜长度全部相同。

我们要求你确定：在恰好使用该机器 $k$ 次后，最多能卖出多少根胡萝卜。请独立地对每个 $k = 1, 2, \ldots, m$ 求解该问题。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains $n$ and $m$ ($1 \le n,m \le 2 \cdot 10^5$), denoting the number of carrots and the maximum possible length of a carrot.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$), denoting the initial carrot sizes.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ and the sum of $m$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 2 \cdot 10^5$），分别表示胡萝卜的数量和胡萝卜可能的最大长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$），表示初始时各胡萝卜的长度。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，且所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output $m$ integers — the answer for each $k=1, 2, \ldots, m$.

对于每个测试用例，输出 $m$ 个整数——分别对应 $k=1, 2, \ldots, m$ 的答案。

In the first test case, the given carrots are $[1, 2, 3, 4, 4]$.

For $k=1$, it is best to choose $x=2$ with the set $[2, 3, 4, 4]$. After the operation, we'll get $[1, 2, 2, 1, 2, 2, 2, 2]$. We can sell $6$ carrots of length $2$.

For $k=2$, it is best to choose $x=2$ with the set $[2, 3, 4, 4]$. After the operation, we'll get $[1, 2, 2, 1, 2, 2, 2, 2]$. For the second operation, it is best to choose $x=1$ with the set of all of the carrots. Resulting in $14$ carrots, all of the same length. We can sell $14$ carrots of length $1$.

在第一个测试用例中，给定的胡萝卜长度为 $[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$ 的胡萝卜。