P7330 “MCOI-07” Dream Fourier Transform

Dream’s redstone computer has been upgraded to the Dream platform. A “Dream program” is a program that runs on the Dream platform. The memory of the Dream platform consists of $5\times2^{17}$ non-negative integers. These memory locations are numbered $0,1,\dots,5\times2^{17}-1$ in order. Initially, all memory locations are $0$. The Dream platform has a feature: the result of the $x$-th operation is stored in memory location $x$, where operations are numbered starting from $0$. A Dream program is an ordered sequence of operations. The operation types are: 1. `>`: input a non-negative integer; the result is the input value. 2. `< x`: output the value stored in memory location `x`; the result is this value. 3. `S c`: the result is a constant non-negative integer $c$, where $0\le c

Dream has a sequence $a_0,a_1,\dots,a_{n-1}$ of length $n$. Dream needs to support two operations: 1. `1 i x`: multiply $a_i$ by $x$. 2. `2 k`: set $x=63912897^k$, and compute $$\sum_{i=0}^{n-1}a_ix^i\pmod{998244353}$$ --- Because of the war, Dream cannot provide the sequence $a$. He can only predict the operations he will perform. Please construct a “Dream program” that reads the array $a$ and outputs the answers to the corresponding queries.

The first line contains two positive integers, representing $n$ and $q$. The next $q$ lines each describe an operation, in the form `1 i x` or `2 k`.

The first line contains a non-negative integer $L$, representing the length of the constructed Dream program. The next $L$ lines each describe an operation. You must ensure that $L\le5\times2^{17}$.

#### Warm reminder $$63912897\equiv3^{\frac{998244352}{2^{12}}}\pmod{998244353}$$ #### Sample explanation When the Dream program input is the sequence `[1,2,3]`, the output is the sequence `[6,347675984]`, which meets the requirements. #### Constraints and conventions **This problem uses bundled testdata.** - Subtask 1 (11 pts): $n,q\le2^8$ - Subtask 2 (19 pts): all query operations are after all update operations. - Subtask 3 (23 pts): $n,q\le2^{10}$ - Subtask 4 (47 pts): no special constraints. For $100\%$ of the testdata, $1\le n,q\le2^{12}$, $0\le i