ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1765. Ошибка 404

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Опытные участники чемпионата Урала приезжают в Екатеринбург заранее, чтобы успеть привыкнуть к суровой погоде, погулять по городу и, конечно, сходить в аквапарк. Однако мало кто знает, что совсем рядом с аквапарком расположен завод №404, прозванный местными жителями «ошибка 404». Найти этот завод действительно непросто, а узнать, что там происходит, — ещё сложнее. К счастью, за его деятельностью можно наблюдать с расположенного неподалёку пешеходного моста. Кажущаяся неподвижность и заброшенность завода обманчива — на самом деле завод работает. Основное направление деятельности завода — ремонт авиационных двигателей.
Недавно на завод поступил заказ на ремонт вышедшего из строя газотурбинного двигателя. Выяснилось, что в турбине оторвались несколько лопаток, в результате чего ось двигателя начала перегружаться. Специалисты завода решили, что для быстрой починки двигателя достаточно удалить часть уцелевших лопаток так, чтобы центр масс оставшихся лопаток вновь стал лежать на оси вращения. Чтобы мощность двигателя упала не слишком сильно, должно быть удалено минимальное количество лопаток. При этом нельзя удалять все лопатки, иначе двигатель вообще не будет работать. Специалисты завода заверили вас, что когда все лопатки были целы, их концы образовывали правильный n-угольник. Подскажите им, какие именно лопатки нужно удалить.
Problem illustration

Исходные данные

В первой строке записаны целые числа n и k (3 ≤ n ≤ 20000; 1 ≤ kn − 1) — исходное количество лопаток турбины и количество оторвавшихся лопаток. Число n имеет не более двух различных простых делителей. В следующей строке через пробел записаны k целых чисел — номера оторвавшихся лопаток в порядке возрастания. Лопатки занумерованы числами от 1 до n по часовой стрелке.

Результат

В первой строке выведите минимальное количество лопаток турбины, которые придётся удалить. Во второй строке выведите через пробел номера этих лопаток в любом порядке. Если возможных ответов несколько, выведите любой. Если нельзя отремонтировать двигатель путём удаления части лопаток, выведите «−1».

Примеры

исходные данныерезультат
12 3
3 4 12
2
8 9
3 1
1
-1
Автор задачи: Игорь Чевдарь (идея — Дмитрий Полетаев)
Источник задачи: XIV чемпионат Урала по спортивному программированию, 10 апреля 2010 г.