Sequence and Queries 13

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$. Write a program that processes the following four kinds of queries.

• 1 x y v: for every $i$ with $x \le i \le y$, replace $A_i$ with $(A_i + v) \bmod (10^9+7)$.
• 2 x y v: for every $i$ with $x \le i \le y$, replace $A_i$ with $(A_i \times v) \bmod (10^9+7)$.
• 3 x y v: for every $i$ with $x \le i \le y$, replace $A_i$ with $v$.
• 4 x y: print $\left(\sum_{i=x}^{y} A_i\right) \bmod (10^9+7)$.

The modulus is always $10^9+7$, and $\bmod$ is the remainder operation.

The first line contains the length $N$ of the sequence. ($1 \le N \le 100000$)

The second line contains $A_1, A_2, \dots, A_N$. ($1 \le A_i \le 10^9$)

The third line contains the number of queries $M$. ($1 \le M \le 100000$)

Each of the next $M$ lines contains one query. ($1 \le x \le y \le N$, $1 \le v \le 10^9$)

For each query of type 4, print the answer on its own line, in the order the queries are given.