U220145 【模板】区间修改主席树2

有若干个长度为 $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$ 时，新建一个版本，使该版本的编号为 $cnt+1$，然后使 $a_{cnt+1,j}=\begin{cases}a_{ver_i,j}&(j\notin [l_i,r_i])\\a_{ver_i,j}\times v_i&(j\in [l_i,r_i])\\\end{cases}$，最后使 $cnt\leftarrow cnt+1$。 3. 当 $opt_i=3$ 时，求 $\sum\limits_{j=l_i}^{j\le r_i}a_{ver_i,j}$ 的值。

无

无

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