C. Поликарп на радиостанции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп — музыкальный редактор на радиостанции. Ему принесли план плей-листа на завтрашний день, являющийся последовательностью a1, a2, ..., an, где ai — группа, которая будет исполнять i-ю песню. Поликарп обожает группы с номерами от 1 до m, но прохладно относится ко всем остальным.

Обозначим как bj количество песен, которые завтра будет играть группа с номером j. Помогите Поликарпу изменить плей-лист так, чтобы минимальное среди чисел b1, b2, ..., bm было как можно больше.

Найдите искомое максимальное значение минимума величин bj (1 ≤ j ≤ m), а также минимальное количество изменений в плей-листе, которое необходимо сделать, чтобы достигнуть такого значения минимума. Одно изменение в плей-листе — это замена группы, которая должна исполнять песню номер i, на любую другую.

Входные данные

В первой строке входных данных записаны два целых числа n и m (1 ≤ m ≤ n ≤ 2000).

Во второй строке следует n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109), где ai равно номеру группы, которая должна исполнять песню i.

Выходные данные

В первую строку выведите два целых числа — максимальное значение минимума величин bj (1 ≤ j ≤ m), где bj — количество песен его любимой группы j, которые будут в изменённом плей-листе, а так же минимальное количество изменений в плей-листе, которое необходимо сделать, чтобы достигнуть этого.

Во вторую строку выведите изменённый плей-лист. Если оптимальных ответов несколько, разрешается вывести любой из них.

Примеры
Входные данные
4 2
1 2 3 2
Выходные данные
2 1
1 2 1 2



Входные данные
7 3
1 3 2 2 2 2 1
Выходные данные
2 1
1 3 3 2 2 2 1



Входные данные
4 4
1000000000 100 7 1000000000
Выходные данные
1 4
1 2 3 4



Примечание

В первом примере после изменений Поликарпа окажется, что первая группа будет исполнять две песни (b1 = 2), как и вторая группа (b2 = 2). Таким образом, минимальное из этих значений равно 2. Большее минимальное значение невозможно получить какими-либо заменами в плей-листе.

Во втором примере после изменений Поликарпа окажется, что первая группа будет исполнять две песни (b1 = 2), вторая группа — 3 песни (b2 = 3), а третья — 2 песни (b3 = 2). Таким образом, наилучшее минимальное значение равно 2.