Первая строка содержит два целых числа $n$ и $q$ ($1 \leq n, q \leq 100\,000$)~--- длина перестановки и количество запросов.

Вторая строка содержит $n$ целых положительных чисел $p_1$, $p_2$, $\ldots$, $p_n$ ($1 \leq p_i \leq n$)~--- элементы перестановки. Гарантируется, что все $p_i$ различны.

Третья строка содержит $q$ целых положительных чисел $b_1$, $b_2$, $\ldots$, $b_q$ ($1 \leq b_i \leq 3$)~--- описание запросов. Число $b_i$ означает, что $i$-й запрос изменения, который нужно применить к перестановке, имеет тип $b_i$. 