#2472. 「九省联考 2018」IIIDX

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Snakes

题目描述

Osu 听过没?那是 Konano 最喜欢的一款音乐游戏,而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在,他在世界知名游戏公司 KONMAI 内工作,离他的梦想也越来越近了。

这款音乐游戏内一般都包含了许多歌曲,歌曲越多,玩家越不易玩腻。同时,为了使玩家在游戏上氪更多的金钱花更多的时间,游戏一开始一般都不会将所有曲目公开,有些曲目你需要通关某首特定歌曲才会解锁,而且越晚解锁的曲目难度越高。

这一天,Konano 接到了一个任务,他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有 nn 首曲目,每首曲目都会有一个难度 dd,游戏内第 ii 首曲目会在玩家 Pass 第 ik\left\lfloor \frac i k \right\rfloor 首曲目后解锁(x\left\lfloor x \right\rfloor 为下取整符号)若 ik=0\left\lfloor \frac i k \right\rfloor = 0,则说明这首曲目无需解锁

举个例子:当 k=2k = 2 时,第 11 首曲目是无需解锁的(12=0\left\lfloor \frac 12 \right\rfloor = 0),第 77 首曲目需要玩家 Pass 第 72=3\left\lfloor \frac 72 \right\rfloor = 3 首曲目才会被解锁。

Konano 的工作,便是安排这些曲目的顺序,使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度,即使得确定顺序后的曲目的难度对于每个 ii 满足 didikd_i \geq d_{\left\lfloor \frac ik \right\rfloor}

当然这难不倒曾经在信息学竞赛摸鱼许久的 Konano。那假如是你,你会怎么解决这份任务呢?

输入格式

从标准输入中读入数据。

1111 个正整数 nn11 个小数 k,nk,n 表示曲目数量,kk 其含义如题所示。

22nn 个用空格隔开的正整数 dd,表示这 nn 首曲目的难度。

输出格式

输出到标准输出中。

输出 11nn 个整数,按顺序输出安排完曲目顺序后第 ii 首曲目的难度。

若有多解,则输出 d1d_1 最大的;若仍有多解,则输出 d2d_2 最大的,以此类推。

样例

样例输入

4 2.0
114 514 1919 810

样例输出

114 810 514 1919

数据范围与提示

测试点编号nn kk dd 特殊限制
11 1n101 \leq n \leq 10 k=2k=2 1d1001 \leq d \leq 100 保证 did_i 互不相同
22 k=3k=3
33 k=1.1k=1.1
44 k=nk=n
55 1<k1001 < k \leq 100
66
77 1n20001\leq n\leq 2000 k=2k=2 1d1091\leq d\leq 10^9 保证 did_i 互不相同
88
99 k=3k=3 保证 did_i 互不相同
1010
1111 1<k1091 < k \leq 10^9 保证 did_i 互不相同
1212
1313 1n5000001\leq n\leq 500000 k=2k=2
1414 k=3k=3
1515 1<k1091<k\leq 10^9 保证 did_i 互不相同
1616
1717
1818
1919
2020