当前没有测试数据。

C - Adjacent Swaps

Score : $300$ points

Problem Statement

$N$ balls are lined up in a row from left to right. Initially, the $i$-th ($1 \leq i \leq N$) ball from the left has an integer $i$ written on it.

Takahashi has performed $Q$ operations. The $i$-th ($1 \leq i \leq Q$) operation was as follows.

• Swap the ball with the integer $x_i$ written on it with the next ball to the right. If the ball with the integer $x_i$ written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let $a_i$ be the integer written on the $i$-th ($1 \leq i \leq N$) ball after the operations. Find $a_1,\ldots,a_N$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq x_i \leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $Q$

$x_1$

$\vdots$

$x_Q$

Output

Print $a_1,\ldots,a_N$, with spaces in between.

5 5
1
2
3
4
5

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with $1$ written on it with the next ball to the right. Now, the balls have integers $2,1,3,4,5$ written on them, from left to right.
• Swap the ball with $2$ written on it with the next ball to the right. Now, the balls have integers $1,2,3,4,5$ written on them, from left to right.
• Swap the ball with $3$ written on it with the next ball to the right. Now, the balls have integers $1,2,4,3,5$ written on them, from left to right.
• Swap the ball with $4$ written on it with the next ball to the right. Now, the balls have integers $1,2,3,4,5$ written on them, from left to right.
• Swap the ball with $5$ written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers $1,2,3,5,4$ written on them, from left to right.

7 7
7
7
7
7
7
7
7

1 2 3 4 5 7 6

10 6
1
5
2
9
6
6

1 2 3 4 5 7 6 8 10 9