Another Update-Query Problem
You will be given an array A of length N and you will have to perform Q operations on that array. There will be two types of operations:
| # | Operation | Description |
|---|---|---|
| 1 | U(L, R, X) | Add x to $ A_i $, where i is in range [l, r] |
| 2 | Q(L, R, D) | Print the output of this series (modulo 1000000007): $ 1A_l + (1+d)A_{l+1} + (1+2d)A_{l+2} + (1+3d)A_{l+3} + … + (1+(r-l)d)A_r $ |
Input
The input starts with an integer T (1 ≤ T ≤ 10), denoting the number of test cases.
The first line of each case has two integers, N (1 ≤ N ≤ 100000) and Q (1 ≤ Q ≤ 100000).
The second line has N integers Ai (1 ≤ Ai ≤ 1000000000), indicating the values of the array.
The following Q lines each has four integers. First of those four integers are C (1 ≤ C ≤ 2).
If C is 1, then it indicates an operation of type 1. The other three integers will be L (1 ≤ L ≤ N), R (1 ≤ R ≤ N, L ≤ R), X (1 ≤ X ≤ 1000000000). And, you will have to perform the operation U(L, R, X).
If C is 2, then it requests an operation of type 2. The other three integers will be L (1 ≤ L ≤ N), R (1 ≤ R ≤ N, L ≤ R), D (1 ≤ D ≤ 1000000000). And, you will have to print the value of Q(L, R, D) modulo 1000000007.
Output
For each case, first print the case number, starting from 1, in a separate line. For each request of operation 2, print the result in a separate line.
Sample
| Input | Output |
|---|---|
2 5 4 2 8 19 9 1 2 2 5 3 2 2 4 6 2 2 5 3 2 2 5 8 3 3 6 7 1 2 2 2 7 1 1 3 8 2 1 2 6 | Case 1: 157 258 157 357 Case 2: 7 119 |
The data set is huge. Please use fast I/O methods.
