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。