题目描述

给定一个长度为 $n$ 的排列 $p$。一个长为 $n$ 的排列是一个由 $1$ 到 $n$ 的 $n$ 个不同整数以任意顺序构成的数组。我们定义排列的 代价 为从 $i = 1$ 到 $n$ 的 $\left(p_i\right)^i$ 之和（排列的第 $i$ 个元素的 $i$ 次幂）。因此，排列 $p$ 的 代价 为

共有 $q$ 个询问，分为三种类型：

• 反转：此后，你的排列 $p$ 被替换为排列 $q$，使得对所有 $i$ 从 $1$ 到 $n$ 有 $q_i = p_{n - i + 1}$。
• 取反：此后，你的排列 $p$ 被替换为排列 $q$，使得对所有 $i$ 从 $1$ 到 $n$ 有 $q_i = n - p_i + 1$。
• 求逆：此后，你的排列 $p$ 被替换为排列 $q$，使得对所有 $i$ 从 $1$ 到 $n$ 有 $q_{p_i} = i$。

注意，每次操作后，$p$ 仍为一个排列。

每次询问后，你需要输出该排列的 代价。

输入格式

第一行包含两个整数 $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$。

输出格式

输出 $q$ 个数，第 $i$ 个数为应用前 $i$ 个询问后，排列的 代价 对 $998\,244\,353$ 取余的结果。

5 5
1 2 3 4 5
1 2 3 1 2

65 3413 3413 65 3413

5 6
5 3 1 4 2
3 3 1 2 3 1

293 303 3225 215 317 3209

提示

样例解释

我们来分析第二个样例。

初始时，$p = [5, 3, 1, 4, 2]$。

第一个询问是类型 $3$，即求逆。此询问后的排列变为 $[3, 5, 2, 4, 1]$。该排列的 代价 为 $3^1 + 5^2 + 2^3 + 4^4 + 1^5 = 3 + 25 + 8 + 256 + 1 = 293$。

第二个询问是类型 $3$，即求逆。此询问后的排列变为 $[5, 3, 1, 4, 2]$。该排列的 代价 为 $5^1 + 3^2 + 1^3 + 4^4 + 2^5 = 5 + 9 + 1 + 256 + 32 = 303$。

第三个询问是类型 $1$，即反转。此询问后的排列变为 $[2, 4, 1, 3, 5]$。该排列的 代价 为 $2^1 + 4^2 + 1^3 + 3^4 + 5^5 = 3225$。

第四个询问是类型 $2$，即取反。此询问后的排列变为 $[4, 2, 5, 3, 1]$。该排列的 代价 为 $4^1 + 2^2 + 5^3 + 3^4 + 1^5 = 215$。

第五个询问是类型 $3$，即求逆。此询问后的排列变为 $[5, 2, 4, 1, 3]$。该排列的 代价 为 $5^1 + 2^2 + 4^3 + 1^4 + 3^5 = 317$。

最后一个询问是类型 $1$，即反转。此询问后的排列变为 $[3, 1, 4, 2, 5]$。该排列的 代价 为 $3^1 + 1^2 + 4^3 + 2^4 + 5^5 = 3209$。

计分

本题的测试数据分为五组。每组仅在通过该组内全部测试以及此前某些组的全部测试后，才能获得分数。注意，某些组不要求通过样例测试。每组的最终得分等于你所有提交的解答中在该组测试上获得的最高分。

翻译由 DeepSeek V4 Pro 完成