给定一个长度为 $n$ 的排列 $p$。长度为 $n$ 的排列是指一个由 $1$ 到 $n$ 的 $n$ 个不同整数以任意顺序组成的数组。我们定义排列的代价为所有 $i$ 从 $1$ 到 $n$ 的量 $(p_i)^i$ 之和（即排列的第 $i$ 个元素提升到 $i$ 次幂）。因此，排列 $p$ 的代价由下式给出： $$\sum_{i=1}^{n} (p_i)^i$$

共有三种类型的 $q$ 个查询：

1. 反转（Reverse）。执行后，你的排列 $p$ 被替换为排列 $q$，使得对于所有 $1 \le i \le n$，都有 $q_i = p_{n-i+1}$。
2. 取反（Invert）。执行后，你的排列 $p$ 被替换为排列 $q$，使得对于所有 $1 \le i \le n$，都有 $q_i = n - p_i + 1$。
3. 求逆（Take the inverse）。执行后，你的排列 $p$ 被替换为排列 $q$，使得对于所有 $1 \le i \le n$，都有 $q_{p_i} = i$。

注意，每次操作后，$p$ 仍然是一个排列。 在每次查询后，你需要输出该排列的代价。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 100\,000$)，分别表示排列的长度和查询的数量。 第二行包含 $n$ 个正整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)，表示排列的元素。保证所有 $p_i$ 互不相同。 第三行包含 $q$ 个正整数 $b_1, b_2, \dots, b_q$ ($1 \le b_i \le 3$)，表示查询的描述。数字 $b_i$ 表示应用于排列的第 $i$ 次修改查询的类型为 $b_i$。

输出格式

输出 $q$ 个数字，其中第 $i$ 个数字表示在应用前 $i$ 次查询后，排列代价对 $998\,244\,353$ 取模的余数。

样例

输入格式 1

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

输出格式 1

65 3413 3413 65 3413

输入格式 2

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

输出格式 2

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

评分

本题的测试包含五个组。仅当通过了该组中的所有测试以及某些先前组中的所有测试时，才会获得该组的分数。注意，某些组不需要通过题目中给出的样例测试。每组测试的最终得分为所有提交方案中在该组测试中获得的最大分数。