Problem Description

Given \( n \) and \( m \), representing \( n \) numbers and \( m \) operations, \( a_i \) represents the \( i \)-th number in the sequence.

You need to implement a data structure that supports two types of operations:
- 1 l r, which means for all \( i \in [l, r] \), set \( a_i \gets \left\lfloor \sqrt{a_i} \right\rfloor \).
- 2 l r, which means for all \( i \in [l, r] \), set \( a_i \gets a_i^2 \).

Finally, you need to output \( \sum_{i=1}^n a_i \) representing the sum of the maintained sequence.

Input Format

The input consists of \( m+2 \) lines.
- The first line contains two positive integers \( n \) and \( m \), as described above.
- The second line contains \( n \) integers \( a_i \), as described above.
- The next \( m \) lines, each containing three positive integers, represent an operation as described above.

Output Format

Output a single integer representing \( \sum_{i=1}^n a_i \), modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

1 1
1
1 1 1

Sample Output #1

1

Sample Input #2

4 2
1 2 3 4
1 2 4
2 1 4

Sample Output #2

7

Sample Input #3

5 5
10 8 10 11 12
2 1 5
1 1 5
1 1 4
2 4 5
1 1 5

Sample Output #3

18

Notes

For \( 5\% \) of the data, \( 1 \le n, m \le 10 \).
For another \( 5\% \) of the data, each 1 l r operation is guaranteed to follow a 2 l r operation.
For another \( 5\% \) of the data, only 1 operations are guaranteed.
For another \( 5\% \) of the data, only 2 operations are guaranteed.
For another \( 5\% \) of the data, all \( l = 1 \) and \( r = n \).
For another \( 5\% \) of the data, \( 1 \le n, m \le 10^3 \).
For \( 100\% \) of the data, \( 1 \le a_i \le 10^9 \) and \( 1 \le n, m \le 2 \times 10^5 \).

We use bundled testing for test cases 7 to 20.

Sample 2 Explanation

见题面 Input 部分

见题面 Output 部分