题目限制

2000 ms 512 M

题目描述

一年之寄在于冬。他的冬天总是与铲雪相伴。

二十四年不间断的铲雪，已经让他和雪相敬如宾。

今年，他本打算把他故乡下北沢的雪铲个干净，全部寄到岜怷的林立高楼间去让他的学生们感受不曾感受的堆雪人，打雪仗的快乐。

但是在这之前，你需要先帮门外疯狂的食雪汉解决一道数据结构题。如果你成功了，他会给你他从上个雪天珍藏到现在的旺旺厚雪烧。

给定一个长度为 $n$ 的正整数序列 $a_{1\sim n}$，你需要维护下列 $m$ 次操作，每次操作为下列两者其一：

$\texttt{0 l r}$：将 $[l,r]$ 内所有数平方，即 $\forall i\in [l,r],a_{i}\leftarrow a_i^2$。 $\texttt{1 l r}$：询问 $[l,r]$ 内所有数倒数的和对 $998244353$ 取模后的结果，即求出 $\sum\limits_{i=l}^r \frac 1{a_i}\bmod 998244353$。

输入格式

第一行，两个整数 $n,m$，含义见题面。

第二行 $n$ 个正整数 $a_{1\sim n}$，表示初始的序列。

第 $3\sim m+2$ 行，每一行按照题面格式描述一个操作。

输出格式

对于每一个形如 $\texttt{1 l r}$ 的操作，输出一行一个整数表示答案。

数据范围

对于 $100\%$ 的数据：$1\le n,m\le 10^5,1\le l\le r\le n,1\le a_i\le 998244352$。

特殊性质 A：保证所有 $0$ 操作均在 $1$ 操作前。

特殊性质 B：保证对于所有操作，$l=1,r=n$。

输入样例 1

5 5
2 6 8 4 3
0 2 4
1 3 4
0 3 5
0 1 5
1 1 5

输出样例 1

920256513
877299769