题目描述

$N$ 个球从左到右排成一行。初始时，从左往右第 $i (1 ≤ i ≤ N)$ 个球上写着整数 $i$。

小高执行了 $Q$ 次操作。第 $i (1 ≤ i ≤ Q)$次操作如下:

将写有整数 $x_i$ 的球与其右侧相邻的球交换。如果写有整数 $x_i$ 的球原本在最右端，则改为与左侧相邻的球交换。

设操作后从左往右第$i (1 ≤ i ≤ N)$个球上写的整数为 $a_i$。请求出 $a_1,...,a_N$。

输入格式

输入按以下格式从标准输入给出:
$N \ Q$
$x_1$
$⋮$
$x_Q$

输出格式

输出 $a_1,...,a_N$，用空格分隔。

样例

5 5
1
2
3
4
5

1 2 3 5 4

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

样例1解释

操作过程如下:

• 交换写有 $1$ 的球与其右侧相邻的球。现在球上的整数从左到右为 $2,1,3,4,5$。
• 交换写有 $2$ 的球与其右侧相邻的球。现在球上的整数从左到右为 $1,2,3,4,5$。
• 交换写有 $3$ 的球与其右侧相邻的球。现在球上的整数从左到右为 $1,2,4,3,5$。
• 交换写有 $4$ 的球与其右侧相邻的球。现在球上的整数从左到右为 $1,2,3,4,5$。
• 交换写有 $5$ 的球与其左侧相邻的球，因为它在最右端。现在球上的整数从左到右为 $1,2,3,5,4$。

数据范围

• $2 ≤ N ≤ 2 × 10^5$
• $1 ≤ Q ≤ 2 × 10^5$
• $1 ≤ x_i ≤ N$
• 所有输入均为整数

来源

• AtCoder ABC250C