2014 Canadian Computing Competition, Stage 1

Problem J4/S1: Party Invitation

You are hosting a party and do not have room to invite all of your friends. You use the following unemotional mathematical method to determine which friends to invite.

Number your friends 1, 2, …, K and place them in a list in this order. Then perform m rounds. In each round, use a number to determine which friends to remove from the ordered list.

The rounds will use numbers r₁, r₂, …, r_m. In round i remove all the remaining people in positions that are multiples of r_i (that is, r_i, 2r_i, 3r_i, …) The beginning of the list is position 1.

Output the numbers of the friends that remain after this removal process.

Input

The first line of input contains the integer K (1 ≤ K ≤ 100). The second line of input contains the integer m (1 ≤ m ≤ 10), which is the number of rounds of removal. The next m lines each contain one integer. The i-th of these lines (1 ≤ i ≤ m) contains r_i (2 ≤ r_i ≤ 100) indicating that every person at a position which is multiple of r_i should be removed.

Output

The output is the integers assigned to friends who were not removed. One integer is printed per line in increasing sorted order.

Sample Input

10
2
2
3

Sample Output

1
3
7
9

Explanation

Initially, our list of invitees is 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. There will be two rounds of removals. After the first round of removals, we remove the even positions (i.e., every second position), which causes our list of invitees to be 1, 3, 5, 7, 9. After the second round of removals, we remove every 3rd remaining invitee: thus, we keep 1 and 3, remove 5 and keep 7 and 9, which leaves us with an invitee list of 1, 3, 7, 9.

All Submissions
Best Solutions

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 27, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)