Description

In your view, there is a row of electrons, each with different energy. What you need to do is sort this row of electrons by swapping adjacent electrons. Sorted means: place the electron with the smallest energy on the far left, closest to the nucleus; place the second smallest in the second position; ...; and place the electron with the largest energy on the far right.
However, you find that $m$ strange forces suddenly appear between the orbitals, making the electron at position $x_i$ unable to be swapped with the electron at position $x_i + 1$.

You strongly believe that this force will overturn current physical theories. What you need to do is make the current row of electrons as sorted as possible in order to discover the pattern.

As sorted as possible means: under the constraints, move the electron with the smallest energy as far left as possible until a barrier appears, and so on.

Input Format

The first line contains two integers $n, m$, representing the number of electrons and the number of forces.
The second line contains $n$ integers describing the initial arrangement of electrons, where the $i$-th number $a_i$ represents the energy of the $i$-th electron.
The third line contains $m$ integers. The $i$-th integer $x_i$ indicates that the electron at position $x_i$ cannot be swapped with the electron at position $x_i + 1$.

Output Format

Output one line with $n$ integers, representing the arrangement that is as sorted as possible under these conditions.

3 0
3 2 1

1 2 3

7 2
1 3 1 4 5 2 1
2 4

1 3 1 4 1 2 5

Hint

For $10\%$ of the testdata, $m = 0$.
For another $20\%$ of the testdata, $n \le 1000, m \le 100$.
For $100\%$ of the testdata, $0 \le n, m \le 5 \times 10^5, 1 \le x_i \le n - 1, 1 \le a_i \le 10^9$.

Translated by ChatGPT 5