← 返回题目列表

Codeforces · 1515/C

C. 凤凰城和塔楼

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

凤凰城有 $$$n$$$ 个高度为 $$$h_1、h_2、\dots、h_n$$$ 的块,并且所有 $$$h_i$$$ 都不超过某个值 $$$x$$$。他计划将所有 $$$n$$$ 块堆叠到 $$$m$$$ 单独的塔中。塔的高度就是其块的高度之和。为了使塔楼看起来更漂亮,两座塔楼的高度差不得严格超过 $$$x$$$。

请帮助凤凰城建造 $$$m$$$ 看起来很漂亮的塔。每座塔必须至少有一个方块,并且必须使用所有方块。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$x$$$ ($$$1 \le m \le n \le 10^5$$$; $$$1 \le x \le 10^4$$$) - 分别是块的数量、要建造的塔的数量以及任何两个塔的最大可接受高度差。

The second line of each test case contains $$$n$$$ space-separated integers ($$$1 \le h_i \le x$$$) — the heights of the blocks.

保证所有测试用例的$$$n$$$总和不会超过$$$10^5$$$。

输出

对于每个测试用例,如果 Phoenix 无法建造看起来很漂亮的 $$$m$$$ 塔,则打印 NO。否则,打印 YES,后跟 $$$n$$$ 整数 $$$y_1, y_2, \dots, y_n$$$,其中 $$$y_i$$$ ($$$1 \le y_i \le m$$$) 是放置第 $$$i$$$ 块的塔的索引。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

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

输出 #1

YES
1 1 1 2 2
YES
1 2 2 3

注意

在第一个测试用例中,第一个塔的高度为 $$$1+2+3=6$$$,第二个塔的高度为 $$$1+2=3$$$。它们的差是$$$6-3=3$$$,不超过$$$x=3$$$,所以塔很漂亮。

在第二个测试用例中,第一个塔的高度为 $$$1$$$,第二个塔的高度为 $$$1+2=3$$$,第三个塔的高度为 $$$3$$$。任意两座塔的最大高度差为$$$3-1=2$$$,不超过$$$x=3$$$,所以塔很漂亮。