P7334 [JRKSJ R1] Beatdown

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

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 one line with one integer, the answer modulo $998244353$.

### Constraints | Test Point | Special Restriction | | :----------: | :----------: | | $1$ | $n,m\le 10$ | | $2$ | Guarantee that for any `1 l r` operation, the previous operation is `2 l r` | | $3$ | Guarantee that there are only `1` operations | | $4$ | Guarantee that there are only `2` operations | | $5$ | Guarantee that all $l=1$ and $r=n$ | | $6$ | $n,m\le 10^3$ | | $7\sim 20$ | No special restrictions | 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