U220120 【模板】区间修改主席树1

有若干个长度为 $n$ 的数组，你需要回答一些问题。 设编号为 $i$ 的数组的第 $j$ 个位置为 $a_{i,j}$。 一开始只有一个数组，编号为 $0$。我们设一个变量 $cnt$，一开始 $cnt=0$。 现在有 $m$ 个操作或询问，第 $i$ 个询问或操作是下列情况之一： 1. 当 $opt_i=1$ 时，新建一个版本，使该版本的编号为 $cnt+1$，然后使 $a_{cnt+1,j}=\begin{cases}a_{ver_i,j}&(j\notin [l_i,r_i])\\a_{ver_i,j}+v_i&(j\in [l_i,r_i])\\\end{cases}$，最后使 $cnt\leftarrow cnt+1$。 2. 当 $opt_i=2$ 时，求 $\sum\limits_{j=l_i}^{j\le r_i}a_{ver_i,j}$ 的值。

第一行三个正整数 $t,n,m$。 如果 $t=1$，那么接下来有一行 $n$ 个整数 $a_{0,1},a_{0,2}\cdots a_{0,n}$。 如果 $t=0$，则没有这一行，编号为 $0$ 的数组的所有位置均为 $0$。 接下来 $m$ 行，每行第一个正整数为 $opt_i$。 如果 $opt_i=1$，接下来有三个正整数 $ver_i,l_i,r_i$，一个非负整数 $v_i$。 如果 $opt_i=2$，接下来有三个正整数 $ver_i,l_i,r_i$。

对于每个询问，输出答案 $\bmod~998244353$ 后的值。

$n,m\le 10^5$。 $t\in[0,1]$。 $a_{0,j},v_i\le 10^6$。 $ver_i,l_i,r_i$ 一定合法。