题目描述

本题使用文件输入输出：输入文件名为 array.in，输出文件名为 array.out。

若数组 $a,S$ 长度均为 $n$，且对于所有 $1\le i\le n$，均满足 $S_i=a_1+a_2+\cdots+a_i$，则数组 $S$ 为数组 $a$ 的前缀和数组。

小 D 有 $n$ 个数组 $A_0,A_1,\cdots,A_{n-1}$，长度均为 $n$。用 $A_{i,j}$ 表示数组 $A_i$ 的第 $j$ 项。已知数组 $A_0$ 的初始值，对于所有 $1\le i<n$，数组 $A_i$ 为数组 $A_{i-1}$ 的前缀和数组。

现在小 D 有 $p$ 个修改操作和 $q$ 个查询操作：

• 对于修改操作，给出 $x,l,r,k$。将数组 $A_x$ 的第 $l\sim r$ 项均增加 $k$。增加后，重新计算除了数组 $A_x$ 外的所有数组，使得对所有 $1\le i<n$，满足数组 $A_i$ 为数组 $A_{i-1}$ 的前缀和数组。
• 对于查询操作，给出 $x,l,r$。请求出数组 $A_x$ 中第 $l\sim r$ 项之和。结果对 $10^9+7$ 取模。

请你执行这些操作，并输出所有查询操作的结果。

输入格式

输入文件名为 array.in。

输入的第一行包含三个整数 $n,p,q$，分别表示数组数量，修改操作数量和询问操作数量。

输入的第二行包含 $n$ 个整数 $A_{0,1},A_{0,2},\dots,A_{0,n}$，表示初始的数列 $A_0$。

接下来 $p+q$ 行，每行输入第一个数字 $o$ 表示操作种类：

• 若 $o=1$，则为修改操作。接下来输入四个数字 $x,l,r,k$，表示将数组 $A_x$ 的第 $l\sim r$ 项增加 $k$。
• 若 $o=2$，则为查询操作。接下来输入三个数字 $x,l,r$，表示查询数组 $A_x$ 中第 $l\sim r$ 项之和。

输出格式

输出文件名为 array.out。

输出 $q$ 行，一行一个非负整数，表示查询操作的结果。结果对 $10^9+7$ 取模。

样例 #1

样例输入 #1

10 2 3
1 2 3 4 5 6 7 8 9 10
1 0 2 4 1
2 0 2 4
2 1 2 4
1 1 3 5 -1
2 2 2 8

样例输出 #1

12
25 
378

提示

【样例 1 解释】

第一次修改后：

• 原数组 $A_0$ 为 $[1,3,4,5,5,6,7,8,9,10]$；
• $A_1$ 为 $[1,4,8,13,18,24,31,39,48,58]$；
• 查询的答案分别为 $3+4+5=12$ 和 $4+8+13=25$。

第二次修改后：

• $A_1$ 为 $[1,4,7,12,17,24,31,39,48,58]$；
• $A_2$ 为 $[1,5,12,24,41,65,96,135,183,241]$；
• 第 $2$ 项到第 $8$ 项的和为 $5+12+24+41+65+96+135=378$。

【样例 2】

见附件 array.zip 中的 array2.in 与 array2.ans。

该样例满足测试点 $4 \sim 7$ 的限制。

【样例 3】

见附件 array.zip 中的 array3.in 与 array3.ans。

该样例满足测试点 $8 \sim 10$ 的限制。

【样例 4】

见附件 array.zip 中的 array4.in 与 array4.ans。

该样例满足测试点 $22 \sim 25$ 的限制。

【数据范围】

对于所有测试点，保证：

• $1\le n\le 300$
• $0\le p,q \le 10^5$
• 对于所有 $1\le i\le n$，均有 $\lvert A_{0,i}\rvert\le 10^9$
• $o\in\{1,2\}$
• 对于所有操作，均有 $0\le x<n$，$1\le l\le r\le n$
• 对于所有操作 $1$，均有 $\lvert k\rvert\le 10^9$

附件

• array.zip