Description

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.

Input

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 a_{1 ~} a_m.

testcases:

1. 1 <= m <= n <= 10000, 1 <= a_i <= n
2. 1 <= m <= n <= 10000, 1 <= a_i <= n
3. 1 <= m <= n <= 10000, 1 <= a_i <= n
4. 1 <= m <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000
5. 1 <= k <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000
6. 1 <= k <= n <= 1000000, 1 <= a_i <= 10000000, n*m <= 300000000

Output

The output has m lines, each line contains a number: who can get the prize.

Sample Input  Download

Sample Output  Download

Partial Judge Code

13129.c

Partial Judge Header

13129.h

Tags

Discuss

Description

In the university, there's a tradition where students give out "All Pass Candy" (歐趴糖), or APCs, to their junior peers before midterms, wishing them to get good grades in the upcoming exams.
This year, CSSA (資工系學會) planned to give out the APCs to all first-year students. Since there are so many students, they want to let the students line up in $N$ lines, and a CSSA member would be in charge of giving out candies at the beginning of each line.
However, on the day of the event, Procat (破貓) took a nap, ended up oversleeping and missed the event. Dogeon (鴿子) was playing maimai (洗衣服), and others were busy with their stuff as well. So, Stiff Waist Beast (挺腰獸) has to give out all the candies by himself. Before that, he has to merge all the lines into one. For the sake of fairness, he wants to merge the lines in a way that the student arriving earlier will get the candy first. Please help him merge all the lines.

• This is a partial judge problem. Input and output are handled by 13584.c. All you have to do is implement the function
  ListNode* mergeLists(ListNode** lists, int n);, which merges the $n$ non-decreasing singly linked lists into one non-decreasing singly-linked list, and returns the head of the merged list.

• The definition of a singly-linked list node:

  typedef struct _ListNode {
    int val;
    struct _ListNode *next;
} ListNode;

• This is a work of fiction. Any resemblance to actual events or persons is entirely coincidental.

Input

• The first line contains an integer $N$, the number of student lines.
• Each of the following $N$ lines starts with an integer $M_i$, followed by $M_i$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i,M_i}$, representing the information of each line.
  • $M_i$ indicates the number of students in the $i$-th line.
  • $a_{i,j}$ indicates the arrival order of the $j$-th student in the $i$-th line.

$N$
$M_1 \quad a_{1,1} \quad a_{1,2} \quad \ldots \quad a_{1,M_1}$
$M_2 \quad a_{2,1} \quad a_{2,2} \quad \ldots \quad a_{2,M_2}$
$\enspace \vdots$
$M_N \quad a_{N,1} \quad a_{N,2} \quad \ldots \quad a_{N,M_N}$

Constraints

• $2 \le N \le 10^5$
• $1 \le M_i \le 10^7$
• $1 \le \sum M_i \le 10^7$
• $1 \le a_{i,j} \le 10^9$
• $a_{i,j - 1} \le a_{i,j}$ for $2 \le j \le M_i$

Output

Single line containing $\sum M_i$ integers, representing the students' arrival order in the merged line. Each integer is followed by a space.
Since this is a partial judge problem, you don't have to worry about the output format.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14219.c

Partial Judge Header

14219.h

Tags

Discuss