Thrilling Program Transformations

Mike has created (n) brand new programs, each with an initial thrill value (a_i). He can perform a sequence of operations to transform the thrill values. There are four types of operations:

1. Addition (Ice Ball): Given an operation of the form 1 l r x, for every index (i) with (l \le i \le r), update (a_i = a_i + x).

2. Multiplication (Soil Ball): Given an operation of the form 2 l r x, for every index (i) with (l \le i \le r), update (a_i = a_i \times x).

3. Block (Fire Ball): Given an operation of the form 3 l r x, for every index (i) with (l \le i \le r), the program's thrill value is blocked from being modified by addition or multiplication operations in the next (x) operations. () The block effect is not overridden by subsequent block operations if the existing block lasts longer.

4. Query: Given an operation of the form 4 l r, output the sum (\sum_{i=l}^{r}a_i) modulo (10^9+7).

To implement the block effect, each program maintains an expiry indicator. When a fire ball operation is applied at operation index (k) with parameter (x), for each affected program the expiry is updated to (\max(\text{current expiry}, k+x)). During an addition or multiplication operation at operation index (k), a program is only modified if (k >) its expiry (i.e. it is not currently blocked).

All arithmetic operations should be performed modulo (10^9+7) when computing the query outputs.

inputFormat

The first line contains two integers (n) and (m) representing the number of programs and the number of operations, respectively.
The second line contains (n) integers (a_1, a_2, \dots, a_n) representing the initial thrill values.
Each of the following (m) lines represents an operation. An operation is either of four integers or three integers:

• If the line contains four integers, the first integer is the operation type (which can be 1, 2, or 3), followed by integers (l, r, x). For type 1, add (x) to every (a_i) for (l \le i \le r). For type 2, multiply every (a_i) by (x) for (l \le i \le r). For type 3, apply a blocking effect for the next (x) operations on the programs in the range ([l, r]).

• If the line contains three integers, it represents a query operation of type 4. Here, the two integers (l, r) specify the range, and you should output ( \sum_{i=l}^{r}a_i ) modulo (10^9+7).
  Note: Operations are processed in order, and the blocking effect is based on the operation index.

outputFormat

For each query operation (type 4), output a single integer representing the sum ( \sum_{i=l}^{r}a_i ) modulo (10^9+7) on a new line.

sample

5 5
1 2 3 4 5
1 1 3 5
3 2 4 2
2 1 5 3
1 3 5 1
4 1 5

55