P7343 【DSOI 2021】电子跃迁

> “如果能证明大统一理论，这个世界将焕然一新。”\ “量子……量子……就差一点……”\ “嘶……哦。**我想我明白了**。”

在你的视野下，出现了一排电子，他们分别拥有不同的能量。你需要做的是通过**将相邻电子互换**的方法，将电子排的有序。**有序**是指：能量最小的电子放到最靠近原子核的左边，将第二小的电子放在第二……将能量最大的电子放在最右边。\ 可是，你发现电子轨道之间忽然出现了 $m$ 个奇怪的力，使位于第 $x_i$ 个位置的电子和位于第 $x_i+1$ 个位置的电子无法进行交换。 你深信这个力将会颠覆当下的物理理论。你需要做的是将现在的一排电子排得**尽量有序**以发现其中规律。 **尽量有序**是指：**在条件下**，能量最小的电子尽量放到左边直至出现屏障，以此类推。

第一行输入两个整数 $n,m$ ，分别表示电子数量和力的数量。\ 第二行输入 $n$ 个整数，表示初始电子排列，其中第 $i$ 个数 $a_i$ 代表第 $i$ 个电子拥有的能量。\ 第三行包含 $m$ 个整数。其中第 $i$ 个整数 $x_i$ 表示位于第 $x_i$ 个位置的电子和位于第 $x_i+1$ 个位置的电子无法进行交换的。

输出一行 $n$ 个整数，表示在这种情况下尽量有序的排列结果。

对于 $10\%$ 的数据，满足 $m=0$；\ 对于另 $20\%$ 的数据，满足 $n \le 1000,m \le 100$；\ 对于 $100\%$ 的数据，满足 $0 \le n,m \le 5 \times 10^5,1 \le x_i \le n-1,1 \le a_i \le 10^9$。