Dream's Sequence Operations

Dream has a sequence \(a_0, a_1, \dots, a_{n-1}\) of length \(n\). He supports two operations:

• 1 i x: Multiply \(a_i\) by \(x\).
• 2 k: Let \(x = 63912897^k\) and compute \[ \sum_{i=0}^{n-1} a_i x^i \pmod{998244353} \]

You need to construct a "Dream Program" that reads the sequence \(a\) and handles the operations, outputting the answer for each query of type 2.

inputFormat

The first line contains two integers \(n\) and \(q\) -- the size of the sequence and the number of operations.

The second line contains \(n\) integers \(a_0, a_1, \dots, a_{n-1}\) representing the sequence.

Each of the next \(q\) lines contains an operation in one of the following formats:

• 1 i x: Multiply \(a_i\) by \(x\) (0-indexed).
• 2 k: Compute \(\sum_{i=0}^{n-1} a_i x^i \pmod{998244353}\) with \(x = 63912897^k\).

outputFormat

For each operation of type 2, output one integer -- the result of the corresponding query.

sample

2 3
1 2
2 0
1 1 3
2 1

3
383477383