Поликарп — музыкальный редактор на радиостанции. Ему принесли план плей-листа на завтрашний день, являющийся последовательностью a1, a2, ..., an, где ai — группа, которая будет исполнять i-ю песню. Поликарп обожает группы с номерами от 1 до m, но прохладно относится ко всем остальным.
Обозначим как bj количество песен, которые завтра будет играть группа с номером j. Помогите Поликарпу изменить плей-лист так, чтобы минимальное среди чисел b1, b2, ..., bm было как можно больше.
Найдите искомое максимальное значение минимума величин bj (1 ≤ j ≤ m), а также минимальное количество изменений в плей-листе, которое необходимо сделать, чтобы достигнуть такого значения минимума. Одно изменение в плей-листе — это замена группы, которая должна исполнять песню номер i, на любую другую.
Выходные данные
В первую строку выведите два целых числа — максимальное значение минимума величин bj (1 ≤ j ≤ m), где bj — количество песен его любимой группы j, которые будут в изменённом плей-листе, а так же минимальное количество изменений в плей-листе, которое необходимо сделать, чтобы достигнуть этого.
Во вторую строку выведите изменённый плей-лист. Если оптимальных ответов несколько, разрешается вывести любой из них.
Примечание
В первом примере после изменений Поликарпа окажется, что первая группа будет исполнять две песни (b1 = 2), как и вторая группа (b2 = 2). Таким образом, минимальное из этих значений равно 2. Большее минимальное значение невозможно получить какими-либо заменами в плей-листе.
Во втором примере после изменений Поликарпа окажется, что первая группа будет исполнять две песни (b1 = 2), вторая группа — 3 песни (b2 = 3), а третья — 2 песни (b3 = 2). Таким образом, наилучшее минимальное значение равно 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 2 3 2
|
2 1
1 2 1 2
|
|
2
|
7 3
1 3 2 2 2 2 1
|
2 1
1 3 3 2 2 2 1
|
|
3
|
4 4
1000000000 100 7 1000000000
|
1 4
1 2 3 4
|