P7334 [JRKSJ R1] 吊打

给出一个长为 $n$ 的正整数序列 $a_{1\sim n}$。接下来有两种操作共 $m$ 次： - `1 l r`，表示将 $a_{l\sim r}$ 开方并下取整，即令 $\forall i\in [l,r],a_i\gets\lfloor\sqrt{a_i}\rfloor$； - `2 l r`，表示将 $a_{l\sim r}$ 平方，即令 $\forall i\in [l,r],a_i\gets a_i^2$。 在所有操作结束后，请你输出 $\displaystyle\sum_{i=1}^na_i$。 由于答案可能很大，你只需要输出其对 $998244353$ 取模的结果即可。

输入共 $m+2$ 行。 第一行输入两个正整数 $n,m$。 第二行输入 $n$ 个正整数 $a_{1\sim n}$。 接下来 $m$ 行，每行 $3$ 个正整数表示一次操作。

输出一行一个整数表示答案对 $998244353$ 取模的结果。

### 数据规模与约定 | 测试点 | 特殊限制 | | :----------: | :----------: | | $1$ | $n,m\le 10$ | | $2$ | 保证一次 `1 l r` 操作上一步是 `2 l r` | | $3$ | 保证只有 `1` 操作 | | $4$ | 保证只有 `2` 操作 | | $5$ | 保证所有的 $l=1$，$r=n$ | | $6$ | $n,m\le 10^3$ | | $7\sim 20$ | 无特殊限制 | 对于所有数据，保证 $1\le n,m\le2\times10^5$，$1\le a_i\le 10^9$。