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

1087. Время забирать камни

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Вероятно, вы знаете игру, в которой два участника по очереди берут из кучки от 1 до 3 камней, и проигрывает тот, кто взял последний камень. Мы немного обобщим эту задачу: будем считать, что оба игрока могут брать не по 1, 2, 3 камня, а по k1, k2, …, km камней. Нас опять будет интересовать вопрос, кто из игроков выигрывает при правильной игре. Гарантируется, что вне зависимости от уже сделанных игроками ходов, всегда возможно сделать очередной ход.

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

В первой строке даны числа n и m (1 ≤ n ≤ 10000; 1 ≤ m ≤ 50) — начальное количество камней в кучке и количество чисел k1, …, km. Во второй строке через пробел находятся числа k1, …, km (1 ≤ kin).

Результат

Выведите число 1, если при правильной игре обоих выигрывает первый игрок (первым берущий камни). Иначе выведите число 2.

Пример

исходные данныерезультат
17 3
1 3 4
2
Автор задачи: Антон Ботов
Источник задачи: Третье командное соревнование школьников Свердловской области по программированию, 4 марта 2001