← 返回题目列表

Codeforces · 723/C

C. 波利卡普在电台

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

Polycarp 是广播电台的音乐编辑。他收到了明天的播放列表,可以表示为序列 a1, a2, ..., an,其中 ai 是一个乐队,演奏第 i 首歌曲。坡旅甲喜欢数字从 1 到 m 的乐队,但他不太喜欢其他乐队。

我们将 j 组明天要表演的歌曲数定义为 bj。 Polycarp 希望以这样的方式更改播放列表,使得数字 b1、b2、...、bm 中的最小值尽可能大。

找到 bj (1 ≤ j ≤ m) 中最小值的最大可能值,以及 Polycarp 需要在播放列表中进行的最小更改次数才能实现它。播放列表中的一个变化是将第 i 首歌曲的表演者替换为任何其他组。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ m ≤ n ≤ 2000)。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109),其中 ai 是第 i 首歌的表演者。

输出

在第一行打印两个整数:bj (1 ≤ j ≤ m) 中最小值的最大可能值,其中 bj 是第 j 个乐队执行更改的播放列表中的歌曲数量,以及 Polycarp 需要在播放列表中进行的最小更改次数。

在第二行打印更改后的播放列表。

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

示例

输入 #1

4 2
1 2 3 2

输出 #1

2 1
1 2 1 2

输入 #2

7 3
1 3 2 2 2 2 1

输出 #2

2 1
1 3 3 2 2 2 1

输入 #3

4 4
1000000000 100 7 1000000000

输出 #3

1 4
1 2 3 4

注意

在第一个样本中,Polycarp 进行更改后,第一支乐队演奏了两首歌曲 (b1 = 2),第二支乐队也演奏了两首歌曲 (b2 = 2)。因此,这些值的最小值等于 2。播放列表中的任何更改都不可能实现更高的最小值。

在第二个样本中,Polycarp 进行更改后,第一支乐队演奏了两首歌曲 (b1 = 2),第二支乐队演奏了三首歌曲 (b2 = 3),第三支乐队也演奏了两首歌曲 (b3 = 2)。因此,最佳最小值为 2。