「MCOI-07」Dream Fourier Transform

Dream 的红石计算机升级为 Dream 平台了。 一个“Dream 程序”为一个在 Dream 平台下执行的程序。 Dream 平台的内存由 $5\times2^{17}$ 个非负整数构成，这些内存位置依次标号为 $0,1,\dots,5\times2^{17}-1$。初始所有内存位置均为 $0$。 Dream 平台有一个特性：第 $x$ 运算的结果在第 $x$ 内存位置存储，其中运算从 $0$ 编号。 Dream 程序为若干运算的有序序列，运算类型为： 1. `>`，表示输入一个非负整数，结果为输入值。 2. `< x`，表示输出内存位置 `x` 所含的值，结果为这个值。 3. `S c`，表示结果为常量非负整数 $c$，其中 $0\le c<998244353$。 4. `+ x y`，表示结果为内存位置 `x` 的值 加 内存位置 `y` 的值。 5. `- x y`，表示结果为内存位置 `x` 的值 减 内存位置 `y` 的值。 6. `* x y`，表示结果为内存位置 `x` 的值 乘 内存位置 `y` 的值。 其中所有运算在模 $998244353$ 意义下计算。

Dream 有一个长度为 $n$ 的序列 $a_0,a_1,\dots,a_{n-1}$。 Dream 要支持两个操作： 1. `1 i x`，表示将 $a_i$ 乘 $x$。 2. `2 k`，表示定 $x=63912897^k$，并且求 $$\sum_{i=0}^{n-1}a_ix^i\pmod{998244353}$$ --- 由战争及时，Dream 无法提供序列 $a$。他只能预测他会进行的操作。请构造一个“Dream 程序”，读入数组 $a$ 并且输出对应询问答案。

第一行两个正整数，分别代表 $n$ 和 $q$。 接下来 $q$ 行，每行描述一个操作，由 `1 i x` 或 `2 k` 格式表示。

第一行一个非负整数 $L$，代表所构造的 Dream 程序长度。 接下来 $L$ 行，每行描述一个运算。 你需要保证 $L\le5\times2^{17}$。

3 3
2 0
1 1 108616
2 114514

15
>
>
>
+ 0 1
+ 3 2
< 4
S 108616
S 716372446
* 1 6
* 8 7
* 7 7
* 2 10
+ 0 9
+ 12 11
< 13

#### 温情提示 $$63912897\equiv3^{\frac{998244352}{2^{12}}}\pmod{998244353}$$ #### 样例解释 当 Dream 程序输入为序列 `[1,2,3]`，输出为序列 `[6,347675984]`，符合要求。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（11 pts）：$n,q\le2^8$ - Subtask 2（19 pts）：所有询问操作在修改操作后面。 - Subtask 3（23 pts）：$n,q\le2^{10}$ - Subtask 4（47 pts）：没有特殊限制。 对于 $100\%$ 的数据，$1\le n,q\le2^{12}$，$0\le i<n$，$0\le x,k<998244353$。