Description

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.

Input Format

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.

Output Format

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}$.

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

Hint

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<n$, $0\le x,k<998244353$.

Translated by ChatGPT 5