题目描述

继上次江桥和七萤都认为自己的数字分析能力很强以后，$n$ 名学生（编号 $1$ 到 $n$）立刻跳出来并且表示自己的数字分析能力也很强。

江桥为了检验他们，初始时给了他们每人一个正整数 $a_i$。

竞赛总共举行 $m$ 轮，在每一轮中，江桥可以选择两种考查方式：

0 x y 分析轮，表示从编号 $x$ 到编号 $y$ 的所有人都将自己当前的数字 $v$ 替换为 $f(v)$。

1 x y 询问轮，表示询问从编号 $x$ 到编号 $y$ 的所有人现在的数字之和。

其中 $f(v)$ 表示 $v$ 最多可以表示成多个少不同的正整数的和。

例如 $f(6) = 3$ $(6 = 1 + 2 + 3)$，$f(4) = 2$ $(4 = 1 + 3)$

江桥知道你很聪明，所以想请你来帮他回答一下每次询问的答案。

输入格式

第一行两个正整数 $n,m$，表示学生数量和竞赛轮数。

第二行 $n$ 个正整数 $a_1,a_2,...,a_n$ 表示初始时每个人的数字。

接下来 $m$ 行，每行 $3$ 个整数 op x y，含义如上所述。

输出格式

对于询问轮，一行一个整数，表示该次询问的答案。由于答案可能过大，你只需要输出答案对 $998244353$ 取模后的值。

10 5
1 2 3 4 5 6 7 8 9 10
0 1 10
1 1 10
1 1 5
0 5 8
1 4 8

24
8
9

样例解释

数据规模与约定

下发文件

下发文件分别对应子任务 $2$、$4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n,m \leq 2 \times 10^{5},1 \leq a_i \leq 10^{17},1 \leq x \leq y \leq n,op \in \{0,1\}$。保证至少有一个询问轮。