Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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$ |

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.

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.

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.

62% Solution Ratio

IamHotEarliest,

Uniquepro.Fastest, 0.1s

Rajib_119Lightest, 4.7 MB

serotoninShortest, 2238B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.