You have two arrays A and B of the same length. You must process three kinds of queries.
\* l r x: add an integer x to all A[i]
where l ≤ i ≤ r.
. l r x: add an integer x to all B[i]
where l ≤ i ≤ r.
? l r: calculate the sum A[l]
· B[l]
+ ... + A[r]
· B[r]
.
Arrays are 1-indexed. Initially, both arrays are filled with zeroes.
The first line contains two space-separated integers n and m: the arrays' lengths and the number of queries, respectively (1 ≤ n, m ≤ 10^5
). The next m lines contain queries in the format described above. In each query 1 ≤ l ≤ r ≤ n and 1 ≤ x < 10^9
+ 7.
For each query of the third type, print its result modulo 10^9
+ 7 on a separate line.