Addition and Multiplication

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given a one dimensional integer array A of length N. You need to maintain the array under Q queries of the following four types. Assume 1based indexing and M = 10^{9} + 7.
Query 1 : 1 x y v
This implies adding v to array A to all the indices from x to y, i.e.,
for (i = x; i <= y; i++)
A_{i} += v;
A_{i} %= M;
Query 2 : 2 x y v
This implies multiplying the scalar v with the array A for all the indices from x to y, i.e.,
for (i = x; i <= y; i++)
A_{i} *= v
A_{i} %= M
Query 3 : 3 x y v
This implies initializing the array A at all the indices from x to y with the value v, i.e.,
for (i = x; i <= y; i++)
A_{i} = v
Query 4 : 4 x y
This is a report query which needs to find the sum of the values in A from x to y, i.e.,
sum = 0;
for (i = x; i <= y; i++)
sum += A_{i}
sum %= M
Output sum.
Note: a%b represents the remainder of a when divided by b.Input
 First line contains two space separated integers N, Q.
 Next line contains N space separated integers denoting the array A.
 Next Q lines contain queries which can be of any of the above four types.
Output
 For each query of type 4, output a single integer corresponding to the answer in a single line.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 1 ≤ Initial value of A_{i} ≤ 10^{9}
 1 ≤ v ≤ 10^{9}
Subtasks
 Subtask 1: Queries are of type 1, 3 and 4. Points  5.
 Subtask 2: Queries are of type 2, 3 and 4. Points  5.
 Subtask 3: Queries are of type 1, 2 and 4. Points  30.
 Subtask 4: All the queries are present. Points  60.
Example
Input: 4 4 1 2 3 4 4 1 4 1 1 3 10 2 2 4 2 4 1 4 Output: 10 69
Explanation
Initial A : [1, 2, 3, 4] Result of first query : 1 + 2 + 3 + 4 = 10 A after second query: [ 11, 12, 13, 4] A after third query : [ 11, 24, 26, 8] Result of fourth query : 11 + 24 + 26 + 8 = 69Author:  devuy11 
Tester:  mugurelionut 
Editorial  http://discuss.codechef.com/problems/ADDMUL 
Tags  devuy11, july15, lazypropagation, medium, segmenttree 
Date Added:  6052014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 