题目描述

给出 $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 解释