Під час проведення І Всеукраїнської Зимової Комп'ютерної школи було вирішено відсвяткувати — «День іменинника». K учасників святкували свій день народження, а інші N вирішили зробити іменинникам солодкий сюрприз і принесли кожен по шоколадці і віддали їх старшій вожатій Марині (усі знають що, для Марини головне — чесність), щоб вона поділила їх між іменинниками.
Марина хоче роздати шоколадки іменинникам так, щоб у кожного з них був однаковий набір шоколадок: однакова кількість молочних шоколадок, шоколадок з ізюмом, чорного шоколаду і інших. Може вийти так, що усі шоколадки порівну розділити не вийде. У цьому випадку їх можна буде використовувати в якості призів на конкурсах.
Марина хоче роздати якомога більше шоколадок іменинникам, проте вона зайнята підготовкою конкурсів. Вона просить Вас визначити оптимальний набір шоколадок, який отримає кожен з K іменинників.
Перший рядок вхідного файлу містить два числа (1 \le N, K \le 10^5) — кількість шоколадок і кількість іменинників відповідно. Другий рядок вхідного файлу містить цілих чисел a_i (1 \le a_i \le 100) — кількість шоколадок кожного типу.
Перший рядок вихідного файлу має містити число — максимальна кількість шоколадок, яку зможе отримати кожен іменинник. Другий рядок повинен містити цілих чисел b_i — типи шоколадок (з урахуванням кількості), які отримає кожен іменинник. Дана послідовність має бути виведена в порядку неспадання.
Приклад 1
Приклад 2
Маючи 4 шоколадки першого типу і 3 другого типу, обидва іменинника отримають по дві шоколадки першого типу і по одній другого.
Усі шоколадки будуть використані в якості призів.
N \le 100, для усіх : a_i = 1 — не менше 20 балів
N \le 100, для усіх : a_i \le 2 — не менше 40 балів
N \le 5000 — не менше 75 балів