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

输入输出样例

输入样例 #1

3 3
2 0
1 1 108616
2 114514

输出样例 #1

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