Operations on Integer Sequence

You are given a sequence of positive integers (a_{1\sim n}) of length (n). There are (m) operations in total of the following two types:

• 1 l r: For every index \(i\) in the interval \([l, r]\), update \(a_i \gets \lfloor \sqrt{a_i} \rfloor\).
• 2 l r: For every index \(i\) in the interval \([l, r]\), update \(a_i \gets a_i^2\).

After performing all operations, output the result of (\displaystyle\sum_{i=1}^{n}a_i) modulo (998244353).

Note: All formulas are given in (\LaTeX) format.

inputFormat

The first line contains two integers (n) and (m) denoting the length of the sequence and the number of operations respectively. The second line contains (n) positive integers (a_1, a_2, \ldots, a_n). Each of the following (m) lines contains an operation in one of the following two forms:

• 1 l r
• 2 l r

Here, \(l\) and \(r\) are 1-indexed positions in the sequence.

outputFormat

Output a single integer: the sum (\displaystyle\sum_{i=1}^{n}a_i) modulo (998244353) after processing all operations.

sample

4 3
4 16 1 9
1 2 3
2 1 1
1 1 4

10