You are given a permutation $p$ of length $n$. A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. We define the \textit{cost} of the permutation as the sum over all $i$ from $1$ to $n$ of the quantity $\left(p_i\right)^i$ (the $i$-th element of the permutation raised to the power of $i$). Thus, the \textit{cost} of the permutation $p$ is given by
$$
\sum\limits_{i=1}^n \left(p_i\right)^i
$$

There are $q$ queries of three types:

\begin{enumerate}
\item Reverse. After this, your permutation $p$ is replaced by the permutation $q$, such that $q_i = p_{n - i + 1}$ for all $i$ from $1$ to $n$.

\item Invert. After this, your permutation $p$ is replaced by the permutation $q$, such that $q_i = n - p_i + 1$ for all $i$ from $1$ to $n$.

\item Take the inverse. After this, your permutation $p$ is replaced by the permutation $q$, such that $q_{p_i} = i$ for all $i$ from $1$ to $n$.
\end{enumerate}

Note that after each operation, $p$ remains a permutation.

After each query, you need to output the \textit{cost} of the permutation.