Segment Tree with Lazy Tags 2

Problem Description

You are given $n$ numbers $a_1, a_2, a_3, \dots, a_n$.

Support $q$ operations:

1. 1 l r d: add $d$ to all $a_i$ with $l\leq i\leq r$.
2. 2 l r d: multiply all $a_i$ with $l\leq i\leq r$ by $d$.
3. 3 l r d: set all $a_i$ with $l\leq i\leq r$ equal to $d$.
4. 4 l r: query $\left(\sum_{i=l}^r a_i\right) \bmod (10^9+7)$.

Input Format

The first line contains two integers $n, q$ ($1\leq n, q\leq 2 \times 10^5$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i\leq 10^9$).

The next $q$ lines each contain an operation of the form 1 l r d, 2 l r d, 3 l r d, or 4 l r, with $1\leq l\leq r\leq n, 1\leq d\leq 10^9$ guaranteed.

Output Format

For each query, output one line containing the answer.

Sample Input

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

Sample Output

15
23
67
44