Frodo and the Monster

Frodo is fighting a monster whose heads are numbered from 1 to K. The monster carries a cybernetic genome, so its heads behave in an unusual way.

When Frodo cuts a head with an odd number X, that head disappears and Y new heads grow in its place, where Y is the largest prime smaller than X. Cutting head 1 grows no new head. The monster's neck holds at most 30000000 heads, so when the number of remaining heads plus Y is greater than 30000000, the head count becomes exactly 30000000.

When Frodo cuts a head with an even number Z, the monster loses every head whose number has the same count of ones in binary as Z. The head numbered Z is one of them. The fight ends once the monster has lost all of its heads.

After every strike, both after new heads grow and after heads are lost, the monster's heads are renumbered starting from 1.

Frodo has no time to check whether a head number is odd or even, so he cuts heads at random. His laser sword records the number of each head at the moment it is cut.

The fight ended in the evening, but Frodo is too tired to count what is left. Write a program that reports the number of heads remaining after the fight.

The first line contains two integers K and N separated by a space ($2 \le K \le 30000000$, $2 \le N \le 200000$), where K is the initial number of heads and N is the number of cuts.

Each of the next N lines contains one integer. These integers give the numbers of the cut heads in order. A head number is always valid, so it never exceeds the head count at the moment of that strike.

Print the number of heads left on the monster's neck after the fight.

Take the first input as an example. Cutting head 5 grows 3 new heads and the total becomes 9. Cutting head 9 grows 7 new heads and the total becomes 15. Cutting head 6 also removes heads 3, 5, 9, 10 and 12. Cutting head 4 then removes heads 8, 2 and 1. Five heads are left when the fight is over.