In Hearthstone, Bladestorm is a strong warrior-class spell card, as shown below. Its effect is to deal one damage to all minions until one minion dies.
In real-game situations, Bladestorm itself cannot deal with complicated boards, so it is usually used together with some other area-of-effect spells. Now Bobo is playing the warrior class in Hearthstone, and his opponent plays minions with pairwise distinct health points $$$a_1,a_2,\dots,a_n$$$ $$$(1\leq a_i\leq n)$$$ sequentially. Bobo has an infinite amount of Bladestorm and spells that can deal $$$k$$$ damages to all minions, and we assume that he may play arbitrary of them in any order. He wonders, each time the opponent plays a minion, what is the minimum number of spells he needs to play to remove all minions on board?
Formally, for each $$$i=1,2,\dots,n$$$, let $$$S_i=\{a_1,a_2,\dots,a_i\}$$$ be the set including the health points of the first $$$i$$$ minions. Bobo wants to compute $$$\text{ans}_i$$$, which is the minimum number of the following operations to perform to make $$$S_i$$$ empty:
- Play Bladestorm.
- Set $$$x\gets x-1$$$ for each $$$x\in S_i$$$
- If $$$S_i$$$ contains at least one $$$0$$$, erase all $$$0$$$s in $$$S_i$$$ and end this operation. Otherwise, goto step 1.
- Play a normal area of effect. Set $$$x\gets x-k$$$ for each $$$x\in S_i$$$ and erase all elements not greater than $$$0$$$ in $$$S_i$$$.
This problem contains multiple test cases. The first line of input contains an integer $$$T$$$ $$$(1\leq T \leq 50\,000)$$$, denoting the number of test cases.
For each test case, the first line of input contains two integers $$$n,k$$$ $$$(1\leq k\leq n\leq 10^5)$$$, denoting the number of minions your opponent plays and the damage of the normal area-of-effect.
Then, one line containing $$$n$$$ pairwise distinct integers $$$a_1,a_2,\dots,a_n$$$ $$$(1\leq a_i\leq n)$$$ follows, denoting the health of each minion the opponent plays sequentially.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot 10^5$$$.
For each test case, output $$$n$$$ integers $$$\text{ans}_1,\text{ans}_2,\dots,\text{ans}_n$$$ in one line, where the $$$i$$$-th $$$(1\leq i\leq n)$$$ integer denotes the minimum number of spells Bobo needs to play to remove all minions on board after the opponent plays the first $$$i$$$ minions.
37 24 7 3 6 1 2 511 310 7 4 9 6 8 5 1 3 2 119 21 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
