U102285 【模板】区间修改主席树

无。

给定一个长度为$n$的数列$num$，你需要进行$m$次操作，每次操作规定如下。 `1 t l r x`在版本$t$的基础上，将$[l,r]$中的数都加上$x$。 `2 t l r`查询版本$t$中$[l,r]$中的数的和。 特别地，每次操作均生成一个新的版本，初始数列$num$为第$0$个版本，答案对$10^9+7$取模。

第一行，两个整数，$n$和$m$。 第二行，用空格隔开的$n$个数字，第$i$个数字表示$num_i$。 接下来的$m$行，每行用空格隔开$4$或$5$个整数，表示如上所述的一次操作。

对于每个操作$2$，输出一行，一个整数，表示答案取模后的结果。

样例1解释：如下表。 | 版本号$t$ | 数列$num$ | 操作 | 输出 | 备注/解释 | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | $0$ | $7 ,6,3,2,4,1,3$ | N/A | N/A | 原始版本 | | $1$ | $12,11,8,2,4,1,3$ | $1\;0\;1\; 3\; 5$ | N/A | 原始版本中的$[1,3]$加上$5$ | | $2$ | $12,13,10,4,6,3,5$ | $1\;1\;2\; 7\; 2$ | N/A | 上一个版本中的$[2,7]$加上$2$ | | $3$ | $12,13,10,4,6,3,5$ | $2\;2\;4\;6$ | 13 | 查询上一个版本$[4,6]$的和 | | $4$ | $13,11,9,2,4,1,3$ | $1\;1\;3\;4\;1$ | N/A | 版本1中的$[3,4]$加上$1$ | | $5$ | $13,11,9,2,4,1,3$ | $2\;4\;1\;5$ | 39 | 求上个版本$[1,5]$的和 | 对于$30\%$的数据，$n,m \le 100$。 对于$100\%$的数据，$n,m \le 10^5$，$0 \le num_i, x \le 10^6$，$1 \le l \le r \le n$。 **运算中，单个节点表示的和在取模前可能高达$10^{11}$，请使用适合的数据类型存储以避免不必要的数据溢出。**