U259681 败者食尘（加强版）

为了卡掉使用主席树过 [【模板】败者食尘](https://www.luogu.com.cn/problem/U258786) 的人 ~~（比如说出题人）~~ ，增加了加强版。 败者食尘在OI中用途广泛，请务必掌握。 ~~败者食尘该普及了，所以此题难度定为普及。~~ **虽然需要卡掉不正确的做法，但此题保证时空限制为std的三倍以上。** **请优化自己的败者食尘以获得线性的空间复杂度。** **~~出题人由于自己感觉麻烦~~ 所以没有加强制在线，但是请自觉使用在线算法。**

给定一个由正整数组成的序列，支持以下三种操作： 1. ```1 l r a``` 给区间 $[l,r]$ 加上 $a$。 2. ```2 l r``` 查询区间 $[l,r]$ 的和。 3. ```3 k``` 向前完全回溯 $k$ 个版本。 关于版本回溯的细节问题可以参考 [【模板】败者食尘](https://www.luogu.com.cn/problem/U258786) 。

第一行两个正整数 $n,m$，分别表示序列长度和操作数。 第二行 $n$ 个整数，表示初始序列。 接下来 $m$ 行，表示操作。

对于所有的操作2，输出相应的答案。

所有输出结果对 998244353 取模。 对于 40% 的数据，有 $n,q \le 5 * 10^3$。 对于 100% 的数据，有 $n,q \le 5 * 10^5$。 存在 20% 的数据不需要取模。 存在另外 20% 的数据没有操作3。