← 返回题目列表

Codeforces · 1849/B

B. 怪物

中文机器翻译题面 查看原题

Monocarp 正在玩另一个电脑游戏。再一次,他的角色正在杀死一些怪物。有 $$$n$$$ 怪物,编号从 $$$1$$$ 到 $$$n$$$,其中第 $$$i$$$ 最初拥有 $$$a_i$$$ 生命值。

Monocarp 的角色有一种能力,可以对当前生命值最高的怪物造成 $$$k$$$ 伤害。如果有多个,则选择索引较小的一个。如果在 Monocarp 使用他的能力后怪物的生命值变得小于或等于 $$$0$$$,那么它就会死亡。

Monocarp 使用他的能力直到所有怪物死亡。你的任务是确定怪物的死亡顺序。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — 怪物的数量和 Monocarp 能力造成的伤害。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 怪物的初始生命值。

所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n$$$ 整数——怪物死亡顺序的索引。

示例

输入 #1

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

输出 #1

2 1 3 
1 2 
3 1 2 4

注意

在第一个示例中,生命值变化如下:$$$[1, 2, \underline{3}] \rightarrow [1, \underline{2}, 1] \rightarrow [\underline{1}, 0, 1] \rightarrow [-1, 0, \underline{1}] \rightarrow [-1, 0, -1]$$$。下次 Monocarp 使用他的能力时将受到伤害的怪物带有下划线。

在第二个示例中,生命值变化如下:$$$[\underline{1}, 1] \rightarrow [-2, \underline{1}] \rightarrow [-2, -2]$$$。

在第三个示例中,生命值变化如下: $$$[2, \underline{8}, 3, 5] \rightarrow [2, \underline{5}, 3, 5] \rightarrow [2, 2, 3, \underline{5}] \rightarrow [2, 2, \underline{3}, 2] \rightarrow [\underline{2}, 2, 0, 2] \rightarrow [-1, \underline{2}, 0, 2] \rightarrow [-1, -1, 0, \underline{2}] \rightarrow [-1, -1, 0, -1]$$$。