The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 100\,000$) --- the length of the permutation and the number of queries.

The second line contains $n$ positive integers $p_1$, $p_2$, $\ldots$, $p_n$ ($1 \leq p_i \leq n$) --- the elements of the permutation. It is guaranteed that all $p_i$ are distinct.

The third line contains $q$ positive integers $b_1$, $b_2$, \ldots, $b_q$ ($1 \leq b_i \leq 3$) --- the description of the queries. The number $b_i$ means that the $i$-th modification query to be applied to the permutation is of type $b_i$. 