区间加

题号：NC229137
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

给出长度为 ${n}$ 的序列 $\{a_n\}$ ，有 ${m}$ 个操作，每个操作为以下几种之一：
1. 给出 ${l,r}$ ，对于 $i\in[l,r]$ ， $a_i=a_i+lowbit(a_i)$ 。
2. 给出 ${l,r}$ ，对于 $i\in[l,r]$ ， $a_i=a_i+highbit(a_i)$ 。
3. 给出 ${l,r}$ ，求 $\sum\limits_{i=l}^{r}a_i$ ，对 ${998244353}$ 取模。
其中， $lowbit(x)=(x)\&(-x)$ ， $highbit(x)=2^k(2^{k}\le x<2^{k+1})$ 。

输入描述:

第一行两个整数  和 ，含义见题目描述。
第二行输入  个整数 ，为给定的序列。
接下来  行，每行输入三个整数 ，表示操作的类型为 ，操作的区间为 。

输出描述:

对于每个操作 ，输出一个整数，为对应的区间和对  取模的结果。

示例1

输入

复制

输出

复制

6
34