[JRKSJ R1] 吊打

给出 $n,m$ 表示有 $n$ 个数，$m$ 次操作，$a_i$ 表示序列中第 $i$ 个数。 你需要写一种数据结构，支持两种操作： - `1 l r`，表示将所有 $i\in[l,r]$，将 $a_i\gets\left\lfloor\sqrt{a_i}\right\rfloor$。 - `2 l r`，表示将所有 $i\in[l,r]$，将 $a_i\gets{a_i}^2$。 最后需要输出 $\sum_{i=1}^na_i$ 表示你维护了这个序列。

输入共 $m+2$ 行。\ 第一行输入两个正整数 $n,m$，意义如上。\ 第二行输入 $n$ 个整数 $a_i$，意义如上。\ 接下来 $m$ 行，每行 $3$ 个正整数，表示一次操作，格式如上。

输出一行一个整数表示 $\sum_{i=1}^na_i$。\ 答案对 $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

对于 $5\%$ 的数据，$1\le n,m\le10$。\ 对于另外 $5\%$ 的数据，保证一次 `1 l r` 操作上一步是 `2 l r`。\ 对于另外 $5\%$ 的数据，保证只有 `1` 操作。\ 对于另外 $5\%$ 的数据，保证只有 `2` 操作。\ 对于另外 $5\%$ 的数据，保证所有的 $l=1$，$r=n$。\ 对于另外 $5\%$ 的数据，$1\le n,m\le10^3$。\ 对于 $100\%$ 的数据，$1\le a_i\le 10^9$，$1\le n,m\le2\times10^5$。 我们对于测试点 $7$ 至 $20$ 采用捆绑测试。 #### 样例 2 解释 | 时刻 | 序列 | | :----------: | :----------: | | $0$ | $[1,2,3,4]$ | | $1$ | $[1,1,1,2]$ | | $2$ | $[1,1,1,4]$ |