There are n people in a circle, numbered from 1 to n in clockwise direction. They are playing a game, and there will be m lucky people that can get the prizes.
Rules of the game:
1. Each prize has a lucky number.
2. Who is counted as 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 who gets a prize shall leave the circle.
6. After someone left the circle, if the new lucky number is odd, count from the next person, otherwise count from the previous person (in clockwise order).
For example:
n = 8
m = 3
lucky number = 3 4 5
The sequence of getting prize is:
first number is 3, so count clockwise starting from 1: 1 2 3
second is 4, so we count from 2, and counterclockwise: 2 1 8 7
last number is 5, so we count from 8, and clockwise: 8 1 2 4 5
Then people 3, 7, 5 can get the prize.
Please use doubly circular linked list to solve this problem.
The first line has two integer n and m, where n is the number of total people, and m is the number of prizes.
The second line has m positive number a1 ~ am.
testcases:
1. 1 <= m <= n <= 10000, 1 <= ai <= n
2. 1 <= m <= n <= 10000, 1 <= ai <= n
3. 1 <= m <= n <= 10000, 1 <= ai <= n
4. 1 <= m <= n <= 1000000, 1 <= ai <= 10000000, n*m <= 300000000
5. 1 <= k <= n <= 1000000, 1 <= ai <= 10000000, n*m <= 300000000
6. 1 <= k <= n <= 1000000, 1 <= ai <= 10000000, n*m <= 300000000
The output has m lines, each line contains a number: who can get the prize.