P16364 [OOI 2026] Permutations and Queries

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: - 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$. - 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$. - 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$. Note that after each operation, $p$ remains a permutation. After each query, you need to output the $\textit{cost}$ of the permutation.

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$.

Output $q$ numbers, the $i$-th of which is the remainder of the $\textit{cost}$ of the permutation modulo $998\,244\,353$, after applying the first $i$ queries.

### Note Let's analyze the second example. Initially, $p = [5, 3, 1, 4, 2]$. The first query is of type $3$, meaning take the inverse. The permutation after this query becomes $[3, 5, 2, 4, 1]$. The \textit{cost} of this permutation is $3^1 + 5^2 + 2^3 + 4^4 + 1^5 = 3 + 25 + 8 + 256 + 1 = 293$. The second query is of type $3$, meaning take the inverse. The permutation after this query becomes $[5, 3, 1, 4, 2]$. The $\textit{cost}$ of this permutation is $5^1 + 3^2 + 1^3 + 4^4 + 2^5 = 5 + 9 + 1 + 256 + 32 = 303$. The third query is of type $1$, meaning reverse. The permutation after this query becomes $[2, 4, 1, 3, 5]$. The $\textit{cost}$ of this permutation is $2^1 + 4^2 + 1^3 + 3^4 + 5^5 = 3225$. The fourth query is of type $2$, meaning invert. The permutation after this query becomes $[4, 2, 5, 3, 1]$. The $\textit{cost}$ of this permutation is $4^1 + 2^2 + 5^3 + 3^4 + 1^5 = 215$. The fifth query is of type $3$, meaning take the inverse. The permutation after this query becomes $[5, 2, 4, 1, 3]$. The $\textit{cost}$ of this permutation is $5^1 + 2^2 + 4^3 + 1^4 + 3^5 = 317$. The last query is of type $1$, meaning reverse. The permutation after this query becomes $[3, 1, 4, 2, 5]$. The $\textit{cost}$ of this permutation is $3^1 + 1^2+ 4^3 + 2^4 + 5^5 = 3209$. ### Scoring The tests for this problem consist of five groups. Points for each group are awarded only if all tests in the group and all tests in some of the previous groups are passed. Note that passing the tests from the statement is not required for some groups. The final score for each group is the maximum score obtained for that group of tests across all submitted solutions. | Group | Points | Additional constraints | < | Required groups | Comment | |:-----:|:------:|:----------------------:|:-:|:---------------:|:-------:| | | | $n$ | $q$ | | | | 0 | 0 | -- | -- | -- | Tests from the statement. | | 1 | 15 | $n \leq 1000$ | $q \leq 1000$ | 0 | | | 2 | 22 | -- | -- | -- | $b_i = b_j$ for all $1 \leq i, j \leq q$ | | 3 | 26 | -- | -- | -- | $b_i \leq 2$ for all $1 \leq i \leq q$ | | 4 | 16 | -- | -- | -- | $p_i = i$ for all $1 \leq i \leq n$ | | 5 | 21 | -- | -- | 0--4 | |