프로도와 괴물

프로도가 괴물과 싸우고 있다. 괴물의 머리에는 1번부터 K번까지 차례로 번호가 붙어 있다. 이 괴물은 사이버네틱 유전자를 지녀서 머리가 특이하게 움직인다.

프로도가 홀수 번호 X인 머리를 자르면 그 머리는 사라지고 같은 자리에 새 머리 Y개가 돋아난다. 여기서 Y는 X보다 작은 소수 중 가장 큰 값이다. 1번 머리를 자르면 새 머리는 돋아나지 않는다. 괴물의 목은 머리를 30000000개까지만 지탱한다. 즉 남은 머리 수와 Y의 합이 30000000을 넘으면 머리 수는 정확히 30000000이 된다.

프로도가 짝수 번호 Z인 머리를 자르면, 괴물은 번호를 이진수로 썼을 때 1의 개수가 Z와 같은 머리를 모두 잃는다. 방금 잘린 Z번 머리도 여기에 포함된다. 괴물이 머리를 전부 잃으면 싸움이 끝난다.

프로도가 한 번 공격할 때마다, 새 머리가 돋아난 뒤에도 머리를 잃은 뒤에도, 괴물의 머리에는 1번부터 번호가 다시 매겨진다.

프로도는 머리 번호가 홀수인지 짝수인지 따져 볼 겨를이 없어서 닥치는 대로 자른다. 다행히 그의 레이저 검은 머리를 자르는 순간 그 머리의 번호를 기록해 둔다.

싸움은 저녁에 끝났지만, 지친 프로도는 남은 머리를 세지 못한다. 싸움이 끝난 뒤 괴물에게 남은 머리 수를 구하는 프로그램을 작성하라.

첫 줄에 정수 K와 N이 공백으로 구분되어 주어진다 ($2 \le K \le 30000000$, $2 \le N \le 200000$). K는 괴물의 처음 머리 수, N은 프로도가 머리를 자른 횟수다.

다음 N개의 줄에는 정수가 한 개씩 주어지며, 잘린 머리의 번호를 순서대로 나타낸다. 머리 번호는 언제나 올바르다. 즉 그 공격 시점의 머리 수를 넘지 않는다.

싸움이 끝난 뒤 괴물의 목에 남은 머리 수를 출력한다.

첫 번째 입력을 예로 들어 보자. 5번 머리를 자르면 새 머리 3개가 돋아나 머리 수가 9가 된다. 9번 머리를 자르면 새 머리 7개가 돋아나 머리 수가 15가 된다. 6번 머리를 자르면 괴물은 3, 5, 9, 10, 12번 머리도 함께 잃는다. 이어서 4번 머리를 자르면 8, 2, 1번 머리를 잃는다. 싸움이 끝나면 머리 5개가 남는다.