Първия ред на стандартния вход съдържа две цели числа $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$. 