You probably know the game where two players in turns take 1 to 3 stones from a pile. Looses the one who takes the last stone. We'll generalize this well known game. Assume that both of the players can take not 1, 2 or 3 stones, but k₁, k₂, …, k_m ones. Again we'll be interested in one question: who wins in the perfect game. It is guaranteed that it is possible to make next move irrespective to already made moves.

The first line contains two integers: n and m (1 ≤ n ≤ 10000; 1 ≤ m ≤ 50) — they are an initial amount of stones in the pile and an amount of numbers k₁, …, k_m. The second line consists of the numbers k₁, …, k_m, separated with a space (1 ≤ k_i ≤ n).

Output 1, if the first player (the first to take stones) wins in a perfect game. Otherwise, output 2.