#P18469. Bladestorm

Bladestorm

Bladestorm

在《炉石传说》中,Bladestorm(剑刃风暴)是一张强力的战士职业法术牌,如下图所示。它的效果是:对所有随从造成 1 点伤害,重复这一过程,直到有随从死亡。

原题中的 Bladestorm 卡牌

在实际对局中,仅靠 Bladestorm 往往不足以处理复杂的场面,因此通常还会配合其它范围伤害法术使用。现在 Bobo 正在使用战士职业,对手依次打出 nn 个随从,其生命值为两两不同的 a1,a2,…,ana_1,a_2,\ldots,a_n,且 1≤ai≤n1\le a_i\le n。

Bobo 拥有无限张 Bladestorm,以及无限张能够对所有随从造成 kk 点伤害的普通范围伤害法术。他可以按任意顺序使用任意数量的法术。每当对手打出一个随从,他都想知道:此时要清除场上所有随从,至少需要使用多少张法术?

形式化地,对每个 i=1,2,…,ni=1,2,\ldots,n,令 Si={a1,a2,…,ai}S_i=\{a_1,a_2,\ldots,a_i\}。求将 SiS_i 变为空集所需的最少操作次数 ansi\mathrm{ans}_i。允许以下两种操作:

  1. 使用一次 Bladestorm:
    • 对每个 x∈Six\in S_i,令 x←x−1x\leftarrow x-1。
    • 如果此时 SiS_i 中有元素为 00,删去其中所有的 00,结束这一次操作;否则重复上一小步。
  2. 使用一次普通范围伤害法术:对每个 x∈Six\in S_i,令 x←x−kx\leftarrow x-k,并删去所有不大于 00 的元素。

每个前缀的答案分别从该前缀的原生命值集合出发计算。

输入格式

输入包含多组测试用例。第一行包含整数 TT(1≤T≤500001\le T\le50000)。

每个测试用例的第一行包含整数 n,kn,k(1≤k≤n≤1051\le k\le n\le10^5),分别表示随从数量和普通范围伤害法术造成的伤害。

第二行包含 nn 个两两不同的整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤n1\le a_i\le n),表示随从被依次打出时的生命值。

保证所有测试用例的 nn 之和不超过 5⋅1055\cdot10^5。

输出格式

对于每个测试用例,输出一行 nn 个整数 $\mathrm{ans}_1,\mathrm{ans}_2,\ldots,\mathrm{ans}_n$,第 ii 个整数表示对手打出前 ii 个随从后,清除这些随从所需的最少法术数。

完整原样例输入

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

完整原样例输出

1 2 3 3 4 4 4
1 2 3 3 3 3 3 4 4 4 4
1 1 2 3 4 4 4 5 5