Just one pile?

There is a single pile containing a certain number of pebbles. In each turn, a player can remove any number of pebbles from the pile, but only according to the specified rules. The player who cannot make a move loses the game.

Your task is to write a program that determines the winner, using an optimal strategy, for the given number of pebbles and rules: either the player who goes first or the one who goes second.

Input

The input consists of several lines, with the number of lines T not exceeding 10. Each line begins with the number of pebbles in the pile M (1 <= M <= $10^6$), followed by the number of rules (allowed moves) N (1 <= N <= 10), and then N integers that describe the rules.

Output

Output a single line containing T characters, each being either 1 or 2, representing the player who will win for each test case.

Examples