\begin{tutorial}{Перестановки и запросы}

\medskip
\textit{Автор задачи: Алексей Михненко}

\textit{Разработчик задачи: Алексей Васильев}
\medskip


Представим перестановку, как набор точек $(i, p_i)$. Тогда операция первого типа переводит все точки $(x, y)$ в $(n - x + 1, y)$. Операция второго типа переводит $(x, y)$ в $(x, n - y + 1)$. Операция третьего типа переводит $(x, y)$ в $(y, x)$.

Заметим, что любым количеством этих операций мы можем получить не больше восьми различных перестановок, которые мы опишем следующим образом. Пусть $f_1, f_2, f_3$~--- три переменные, которые принимают значение $0$ или $1$.

Пусть $p$~--- наша изначальная перестановка, дальше по порядку применяем к ней следующие модификации:

\begin{enumerate}

\item Если $f_1 = 1$, то делаем операцию третьего типа (то есть переводим $(x, y)$ в $(y, x)$).

\item Если $f_2 = 1$, то делаем операцию первого типа (то есть переводим $(x, y)$ в $(n - x + 1, y)$).

\item Если $f_3 = 1$, то делаем операцию второго типа (то есть переводим $(x, y)$ в $(x, n - y + 1)$).

\end{enumerate}

Изначально предподсчитаем стоимость восьми перестановок, которые соответствуют каждому возможному набору переменных $f_1, f_2, f_3$.

Теперь будем поддерживать текущие переменные $f_1, f_2, f_3$, которые изначально равны нулю.

\begin{itemize}

\item Запрос первого типа: заменяем $f_2$ на $1 - f_2$.

\item Запрос второго типа: заменяем $f_3$ на $1 - f_3$.

\item Запрос третьего типа: заменяем $f_1$ на $1 - f_1$ и меняем местами $f_2$ и $f_3$.

\end{itemize}

Таким образом мы после каждого запроса поддерживаем актуальные переменные $f_1, f_2, f_3$ и выводим предподсчитанную стоимость для таких флагов. Время работы $O(n \log n + q)$, где $\log$ от бинарного возведения в степень для подсчета стоимости.

\end{tutorial}
