题目描述

给出一个长为 $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 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

提示

数据规模与约定

测试点	特殊限制
$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$。