Practice on Toph

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

Another Update-Query Problem

By pariah · Limits 1s, 512 MB

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:

#OperationDescription
1U(L, R, X)Add x to $ A_i $, where i is in range [l, r]
2Q(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

InputOutput
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.


Discussion
Statistics

64% Solution Ratio

IamHotEarliest, Jul '17

Uniquepro.Fastest, 0.1s

Rajib_119Lightest, 4.7 MB

Uniquepro.Shortest, 2454B

Submit

Login to submit