Description

You are given a positive integer sequence $a_{1\sim n}$ of length $n$. Then there are $m$ operations of two types:

• 1 l r means taking the square root of $a_{l\sim r}$ and rounding down, that is, set $\forall i\in [l,r],a_i\gets\lfloor\sqrt{a_i}\rfloor$;
• 2 l r means squaring $a_{l\sim r}$, that is, set $\forall i\in [l,r],a_i\gets a_i^2$.

After all operations are finished, output $\displaystyle\sum_{i=1}^na_i$.

Since the answer may be very large, you only need to output it modulo $998244353$.

Input Format

The input has $m+2$ lines.

The first line contains two positive integers $n,m$.

The second line contains $n$ positive integers $a_{1\sim n}$.

The next $m$ lines each contain $3$ positive integers describing one operation.

Output Format

Output one line with one integer, the answer modulo $998244353$.

1 1
1
1 1 1

1

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

7

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

18

Hint

Constraints

For all testdata, it is guaranteed that $1\le n,m\le2\times10^5$ and $1\le a_i\le 10^9$.

Translated by ChatGPT 5