There are n people, numbered 1 to n, in a circle and arranged in clockwise. They are playing a game, kth lucky people can get the prize.
The following are rules of the game:
1. Each prize has a lucky number.
2. Who count the lucky number can get a prize.
3. If the lucky number is odd, count clockwise.
4. If the lucky number is even, count counterclockwise.
5. The student that gets prize will leave the circle.
6. After someone leave the circle, if the new lucky number is odd, count from the next person, otherwise count from the previous person.
For example:
n = 8
m = 3
lucky number = 3 4 5
The sequence of getting prize is:
1 2 3
2 1 8 7
8 1 2 4 5
Then people 3, 5, 7 can get the prize.
Please use doubly circular linked list to solve this problem.
The first line has two integer n and k, where n is the number of total people, and k is the number of prizes.
The second line has k positive number a1 ~ ak.
testcases:
1. 1 <= k <= n <= 10000, 1 <= ak <= n
2. 1 <= k <= n <= 10000, 1 <= ak <= n
3. 1 <= k <= n <= 10000, 1 <= ak <= n
4. 1 <= k <= n <= 1000000, 1 <= ak <= 10000000, n*k <= 300000000
5. 1 <= k <= n <= 1000000, 1 <= ak <= 10000000, n*k <= 300000000
6. 1 <= k <= n <= 1000000, 1 <= ak <= 10000000, n*k <= 300000000
The output has k lines, each line contains a number: who can get the prize.