Competitions

# Counting-Out

n children, standing in a circle, are using counting-outs to determine who will leave the circle. It means, they recite counting-out rhymes, pointing each rhyme’s word on next (by circle) child. The child being pointed on at the last word of the rhyme leaves the circle.

The process repeats k (1kn) times, restarting from the child following the one who just had left the circle. Counting starts from lower numbers to higher, but counting-out rhymes are different.

Write a program which reads number of children, number of counting-out rhymes, and numbers of words in used counting-out rhymes, and finds the order in which children will leave the circle.

Input

The first line contains space separated number of children n (1n1018) and number of used counting-out rhymes k (1k ≤ min(n, 105)). The second line contains k integers (each in range 1ai1018) - numbers of words in the counting-out rhymes, used the 1st, the 2nd, …, the k-th time.

Output

The only line of the output should contain space-separated sequence of k numbers - the numbers of the children leaving the circle after the corresponding counting-out. Initially, children are numbered from 1 to k, and the 1st is the child who is pointed on when reciting the 1st word of the 1st counting-out rhyme. Further, each child keeps the same number, irrespectively of how children leave the circle.

Time limit 3 seconds
Memory limit 64 MiB
Input example #1
10 5
2 7 1 8 2

Output example #1
2 9 10 1 4

Input example #4
8 3
10 1 2

Output example #4
2 3 5

Source 2014 ACM-ICPC Ukraine, 2nd Round Ukraine, September 13, Problem I