题目描述

$N$ 个球左右排成一列。开始，从左到右的第 $i (1 \le i \le N)$ 个球写着整数 $i$。

高桥君进行了 $Q$ 回的操作。第 $i (1 \le i \le Q)$ 次操作如下:

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

设操作后从左往右第 $i(1 \le i \le N)$ 个球上写的整数为 $a_i$。

请求出 $a_1, \dots, a_N$。

输入格式

第一行为 $N$, $Q$。

第 $i+1$ 行为 $a_i$。

输出格式

从左到右输出操作后的球上分别写着的数字.

样例 #1

样例输入 #1

5 5
1
2
3
4
5

样例输出 #1

1 2 3 5 4

样例 #2

样例输入 #2

7 7
7
7
7
7
7
7
7

样例输出 #2

1 2 3 4 5 7 6

样例 #3

样例输入 #3

10 6
1
5
2
9
6
6

样例输出 #3

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\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ Q\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ x_i\ \leq\ N$
• 所有输入均为整数