P7343 [DSOI 2021] Electron Transition.

> "If we can prove the grand unified theory, this world will be completely renewed."\ > "Quantum... quantum... we are just a little bit away..."\ > "Hiss... oh. **I think I understand**."

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.

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 one line with $n$ integers, representing the arrangement that is as sorted as possible under these conditions.

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