Вероятно, вы знаете игру, в которой два участника по очереди берут из кучки от 1 до 3 камней, и проигрывает тот, кто взял последний камень. Мы немного обобщим эту задачу: будем считать, что оба игрока могут брать не по 1, 2, 3 камня, а по k₁, k₂, …, k_m камней. Нас опять будет интересовать вопрос, кто из игроков выигрывает при правильной игре. Гарантируется, что вне зависимости от уже сделанных игроками ходов, всегда возможно сделать очередной ход.

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

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