408150: GYM103003 B DDDFT

After the debacle of Dream's previous redstone computer, Dream has now laid the job of programming the computer to you.

The memory of Dream's redstone computer can be visualized as an array of $$$5\cdot 2^{17}$$$ integers, labeled $$$0,1,2,\dots,5\cdot 2^{17}-1$$$ respectively. Initially, the value of all positions in this array is $$$0$$$.

We will refer to the memory with label $$$x$$$ as memory $$$x$$$.

Define a Dream program as a program that runs on Dream's redstone computer. A Dream program is designed such that the result of the $$$x$$$-th instruction is stored in memory $$$x$$$, where $$$x$$$ starts from $$$0$$$. This means that the maximal instruction count of a valid Dream program is $$$5\cdot2^{17}$$$.

A Dream program can be represented as a sequence of instructions. These instructions can be one of the following:

• >: read an integer from the input of the computer. Result is this read value.
• < $$$x$$$: output the integer at memory $$$x$$$. Result is this outputted value.
• S $$$c$$$: Result is the value $$$c$$$, where $$$0\le c<998244353$$$.
• + $$$x$$$ $$$y$$$: Result is the sum of memory $$$x$$$ and memory $$$y$$$.
• - $$$x$$$ $$$y$$$: Result is the difference of memory $$$x$$$ and memory $$$y$$$.
• * $$$x$$$ $$$y$$$: Result is the product of memory $$$x$$$ and memory $$$y$$$.

All arithmetic operations are done modulo $$$998244353$$$.

Now, Dream asks you to implement the Dream Dynamic Discrete Fourier Transform on an array $$$a_0,a_1,\dots,a_{n-1}$$$ in a Dream program. Specifically, the Dream program shall execute $$$q$$$ of these operations:

• 1 $$$i$$$ $$$x$$$: Multiply $$$a_i$$$ by $$$x$$$.
• 2 $$$k$$$: Define $$$x=63912897^k$$$. Output the value $$$$$$\left(\sum_{i=0}^{n-1}a_ix^i\right)\bmod 998244353$$$$$$

Note that you are not given this array! This array (in order of increasing indices) will be the input of the Dream program. You are instead asked to output a Dream program. The Dream program that you output should have output equal to the sequential answers for queries of type $$$2$$$ when given any array as input. For more details, refer to the input.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le2^{12}$$$).

Each of the following $$$q$$$ lines contain a description of a query, either of the form 1 $$$i$$$ $$$x$$$ ($$$0\le i<n$$$, $$$0\le x<998244353$$$) or 2 $$$k$$$ ($$$0\le k<998244353$$$).

Following this will be some data intended for the checker.

In the first line, output an integer $$$L$$$, the length of your constructed Dream program. This integer should satisfy $$$0\le L\le 5\cdot2^{17}$$$.

In the following $$$L$$$ lines, describe your Dream program, with a description of one instruction per line.

• In the first subtask, worth $$$11$$$ points, $$$n,q\le2^8$$$.
• In the second subtask, worth $$$19$$$ points, all queries are after all modifications.
• In the third subtask, worth $$$23$$$ points, $$$n,q\le2^{10}$$$.
• In the fourth subtask, worth $$$47$$$ points, no additional constraints are imposed.

3 3
2 0
1 1 108616
2 114514
5
3 1 2 3
2 6 347675984
3 249562194 77997864 782218748
2 111534453 645770907
3 427868729 963824933 961269789
2 356474745 375144741
3 716807646 177923670 143374138
2 39861101 981112147
3 541186351 838003166 750524701
2 133225512 814133617

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

The following fact may or may not be useful:

$$$$$$63912897\equiv3^{\frac{998244352}{2^{12}}}\pmod{998244353}$$$$$$

In the first sample, when the input of the Dream program is [1,2,3], the output is [6,347675984], which is correct.