#include<iostream>
#include<vector>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#define M 1000000007
#define sum(a,b) ((a)+(b))
#define gc getchar
typedef long long int ll;
using namespace std;
template<class T>
class SegmentTree{
ll *tree, *lazy;
int size;
//tree.resize(MAX);
//lazy.resize(MAX);
public:
SegmentTree(int N)
{
int x = (int)(ceil(log2(N)))+1;
size = 2*(int)pow(2,x);
tree = new ll[size];
lazy = new ll[size];
memset(tree,-1,sizeof(tree));
memset(lazy,0,sizeof(lazy));
}
void build_tree(int a, int b, int index, T *A) {
//cout << "node: " << index << endl;
if(a == b) {
tree[index] = A[a];
return;
}
int mid = (a+b)/2;
build_tree(a, mid, index*2+1, A);
build_tree(1+mid, b, index*2+2, A);
tree[index] = sum(tree[index*2+1], tree[index*2+2]);
// cout << "value["<<index<<"] = " << tree[index] << endl;
}
int query_sum(int node, int a, int b, int i, int j) {
//cout << "a = " << a << " b= " << b <<" i= " <<i << " j = " << j << endl;
if(a > b || a > j || b < i) return 0;
if(lazy[node] != 0) {
tree[node] += lazy[node];
tree[node] %= M;
if(a != b) {
lazy[node*2+1] += lazy[node];
lazy[node*2+2] += lazy[node];
}
lazy[node] = 0;
}
if(a >= i && b <= j){
// cout << "now: " << tree[node];
return tree[node];
}
int mid = (a+b)/2;
int q1 = query_sum(node*2+1, a, mid, i, j);
int q2 = query_sum(node*2+2, 1+mid, b, i, j);
int res = sum(q1,q2)%M;
return res;
}
void query_add_update(int node, int a, int b, int i, int j, int val) // 'val' is the difference here
{
// cout << "NOW NODE: " << node << endl;
if(lazy[node] != 0)
{
// cout << "CHECK 1" << endl;
//tree[node] += lazy[node];
//cout << "tree["<<node<<"] = " << tree[node] << endl;
if(a!=b){
lazy[2*node+1] += lazy[node];
lazy[2*node+2] += lazy[node];
// cout << "lazy["<<2*node+1<<"] = " << lazy[node*2+1] << endl;
//cout << "lazy["<<2*node+2<<"] = " << lazy[node*2+2] << endl;
}
lazy[node] = 0;
}
if(a > b || a > j || b < i)
return;
if(a >= i && b <= j)
{
//cout << "check 2" << endl;
//cout << "tree["<<node<<"] = " << tree[node] << endl;
tree[node] += val;
tree[node] %= M;
//cout << "tree["<<node<<"] = " << tree[node] << endl;
if(a!=b)
{
lazy[2*node+1] += val;
lazy[2*node+2] += val;
// cout << "lazy["<<2*node+1<<"] = " << lazy[node*2+1] << endl;
//cout << "lazy["<<2*node+2<<"] = " << lazy[node*2+2] << endl;
}
else
return;
}
int mid = (a+b)/2;
query_add_update(node*2+1, a, mid, i, j, val);
query_add_update(node*2+2, 1+mid, b, i, j, val);
tree[node] = sum(tree[node*2+1], tree[node*2+2]);
}
void query_mul_update(int node, int a, int b, int i, int j, int val)
{
if(lazy[node]!=0)
{
// tree[node] *= lazy[node];
//tree[node] %= M;
if(a!=b){
lazy[2*node+1] += lazy[node];
lazy[2*node+2] += lazy[node];
}
lazy[node] = 0;
}
if(a > b || a > j || b < i)
return;
if(a >= i && b <= j)
{
tree[node] *= val;
tree[node] %= M;
if(a!=b)
{
lazy[node*2+1] += val;
lazy[node*2+2] += val;
}
else
return ;
}
query_mul_update(node*2+1, a, (a+b)/2, i, j, val);
query_mul_update(node*2+2, 1+(a+b)/2, b, i, j, val);
tree[node] = sum(tree[node*2+1], tree[node*2+2]);
}
void query_setvalue(int node, int a, int b, int i, int j, int val)
{
if(lazy[node] != 0)
{
tree[node] += lazy[node];
if(a!=b){
lazy[2*node+1] += lazy[node];
lazy[2*node+2] += lazy[node];
}
lazy[node] = 0;
}
if(a > b || a > j || b < i)
return;
if(a >= i && b <= j)
{
tree[node] = val;
if(a!=b)
{
lazy[2*node+1] = val;
lazy[2*node+2] = val;
}
else
return ;
}
query_setvalue(node*2+1, a, (a+b)/2, i, j, val);
query_setvalue(node*2+2, 1+(a+b)/2, b, i, j, val);
tree[node] = sum(tree[node*2+1], tree[node*2+2]);
}
//Additional Function
void print(int node, int a, int b)
{
if(a>b)
return;
if(a==b){
cout << tree[node] << "("<<node<<")"<<" " ;
return;
}
int mid = (a+b)/2;
print(2*node+1,a,mid);
print(2*node+2,mid+1,b);
}
};
template <class T>
class Input{
public:
T read_int() {
char c = gc();
while(c<'0' || c>'9')
c = gc();
T ret = 0;
while(c>='0' && c<='9') {
ret = 10 * ret + c - 48;
c = gc();
}
return ret;
}
};
int main(void)
{
Input<ll>ip;
ll ans,x,y, v;
ll *ar, answer;
ll n = ip.read_int();
ll q = ip.read_int();
ar = (ll*)malloc(n*sizeof(ll));
for(int i=0;i<n;i++)
ar[i] = ip.read_int();
SegmentTree<ll> st(n);
st.build_tree(0,n-1,0,ar);
while(q--)
{
ans = ip.read_int();
x = ip.read_int();
y = ip.read_int();
if(ans!=4)
v = ip.read_int();
x -= 1;
y -= 1;
if(ans==1)
st.query_add_update(0,0,n-1,x,y,v);
if(ans==2)
st.query_mul_update(0,0,n-1,x,y,v);
if(ans==3)
st.query_setvalue(0,0,n-1,x,y,v);
if(ans==4){
answer = (ll)st.query_sum(0,0,n-1,x,y);
cout << answer << endl;
}
// st.print(0,0,n-1);
//cout << endl;
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8Y21hdGg+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8Y3N0ZGxpYj4KI2RlZmluZSBNIDEwMDAwMDAwMDcKI2RlZmluZSBzdW0oYSxiKSAoKGEpKyhiKSkKCiNkZWZpbmUgZ2MgZ2V0Y2hhcgp0eXBlZGVmIGxvbmcgbG9uZyBpbnQgbGw7Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCnRlbXBsYXRlPGNsYXNzIFQ+CmNsYXNzIFNlZ21lbnRUcmVlewoKICAgIGxsICp0cmVlLCAqbGF6eTsKICAgIGludCBzaXplOwogICAgLy90cmVlLnJlc2l6ZShNQVgpOwogICAgLy9sYXp5LnJlc2l6ZShNQVgpOwogICAgcHVibGljOgogICAgIFNlZ21lbnRUcmVlKGludCBOKQogICAgIHsKICAgICAgICAgIGludCB4ID0gKGludCkoY2VpbChsb2cyKE4pKSkrMTsKICAgICAgICAgIHNpemUgPSAyKihpbnQpcG93KDIseCk7CiAgICAgICAgICB0cmVlID0gbmV3IGxsW3NpemVdOwogICAgICAgICAgbGF6eSA9IG5ldyBsbFtzaXplXTsKICAgICAgICAgIG1lbXNldCh0cmVlLC0xLHNpemVvZih0cmVlKSk7CiAgICAgICAgICBtZW1zZXQobGF6eSwwLHNpemVvZihsYXp5KSk7CiAgICAgfQogICAgIHZvaWQgYnVpbGRfdHJlZShpbnQgYSwgaW50IGIsIGludCBpbmRleCwgVCAqQSkgewoKICAgICAgICAgLy9jb3V0IDw8ICJub2RlOiAiIDw8IGluZGV4IDw8IGVuZGw7CgogICAgICAgIGlmKGEgPT0gYikgewogICAgCXRyZWVbaW5kZXhdID0gQVthXTsKCQlyZXR1cm47CiAgICAgICAgfQogICAgICAgIGludCBtaWQgPSAoYStiKS8yOwogICAgICAgIGJ1aWxkX3RyZWUoYSwgbWlkLCBpbmRleCoyKzEsIEEpOwogICAgICAgIGJ1aWxkX3RyZWUoMSttaWQsIGIsIGluZGV4KjIrMiwgQSk7CgogICAgICAgIHRyZWVbaW5kZXhdID0gc3VtKHRyZWVbaW5kZXgqMisxXSwgdHJlZVtpbmRleCoyKzJdKTsKICAgICAgIC8vIGNvdXQgPDwgInZhbHVlWyI8PGluZGV4PDwiXSA9ICIgPDwgdHJlZVtpbmRleF0gPDwgZW5kbDsKCiAgICB9CgogICAgaW50IHF1ZXJ5X3N1bShpbnQgbm9kZSwgaW50IGEsIGludCBiLCBpbnQgaSwgaW50IGopIHsKCiAgICAgICAgLy9jb3V0IDw8ICJhID0gIiA8PCBhIDw8ICIgYj0gIiA8PCBiIDw8IiBpPSAiIDw8aSA8PCAiIGogPSAiIDw8IGogPDwgZW5kbDsKCiAgICAgICAgaWYoYSA+IGIgfHwgYSA+IGogfHwgYiA8IGkpIHJldHVybiAwOwoKICAgICAgICBpZihsYXp5W25vZGVdICE9IDApIHsKICAgICAgICAgICAgdHJlZVtub2RlXSArPSBsYXp5W25vZGVdOwogICAgICAgICAgICB0cmVlW25vZGVdICU9IE07CiAgICAgICAgICAgIGlmKGEgIT0gYikgewogICAgICAgICAgICAgICAgbGF6eVtub2RlKjIrMV0gKz0gbGF6eVtub2RlXTsKICAgICAgICAgICAgICAgIGxhenlbbm9kZSoyKzJdICs9IGxhenlbbm9kZV07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgbGF6eVtub2RlXSA9IDA7CiAgICAgICAgfQoKICAgICAgICBpZihhID49IGkgJiYgYiA8PSBqKXsKICAgICAgICAgICAvLyBjb3V0IDw8ICJub3c6ICAiIDw8IHRyZWVbbm9kZV07CiAgICAgICAgICAgIHJldHVybiB0cmVlW25vZGVdOwoKICAgICAgICB9CgogICAgICAgIGludCBtaWQgPSAoYStiKS8yOwoKICAgICAgICBpbnQgcTEgPSBxdWVyeV9zdW0obm9kZSoyKzEsIGEsIG1pZCwgaSwgaik7CiAgICAgICAgaW50IHEyID0gcXVlcnlfc3VtKG5vZGUqMisyLCAxK21pZCwgYiwgaSwgaik7CgogICAgICAgIGludCByZXMgPSBzdW0ocTEscTIpJU07CgogICAgICAgIHJldHVybiByZXM7CiAgICB9CgogICAgdm9pZCBxdWVyeV9hZGRfdXBkYXRlKGludCBub2RlLCBpbnQgYSwgaW50IGIsIGludCBpLCBpbnQgaiwgaW50IHZhbCkgLy8gJ3ZhbCcgaXMgdGhlIGRpZmZlcmVuY2UgaGVyZQogICAgewogICAgICAvLyAgY291dCA8PCAiTk9XIE5PREU6ICIgPDwgbm9kZSA8PCBlbmRsOwogICAgICAgIGlmKGxhenlbbm9kZV0gIT0gMCkKICAgICAgICB7CiAgICAgICAgLy8gY291dCA8PCAiQ0hFQ0sgMSIgPDwgZW5kbDsKICAgICAgICAvL3RyZWVbbm9kZV0gKz0gbGF6eVtub2RlXTsKCiAgICAgICAgIC8vY291dCA8PCAidHJlZVsiPDxub2RlPDwiXSA9ICIgPDwgdHJlZVtub2RlXSA8PCBlbmRsOwoJCWlmKGEhPWIpewogICAgICAgICAgICBsYXp5WzIqbm9kZSsxXSArPSBsYXp5W25vZGVdOwogICAgICAgICAgICBsYXp5WzIqbm9kZSsyXSArPSBsYXp5W25vZGVdOwogICAgICAgICAgIC8vIGNvdXQgPDwgImxhenlbIjw8Mipub2RlKzE8PCJdID0gIiA8PCBsYXp5W25vZGUqMisxXSA8PCBlbmRsOwogICAgICAgICAgICAvL2NvdXQgPDwgImxhenlbIjw8Mipub2RlKzI8PCJdID0gIiA8PCBsYXp5W25vZGUqMisyXSA8PCBlbmRsOwoJCX0KICAgICAgICAgICAgbGF6eVtub2RlXSA9IDA7CiAgICAgICAgfQoKICAgICAgICBpZihhID4gYiB8fCBhID4gaiB8fCBiIDwgaSkKICAgICAgICAgICAgcmV0dXJuOwoKICAgICAgICBpZihhID49IGkgJiYgYiA8PSBqKQogICAgICAgIHsKICAgICAgICAgICAgLy9jb3V0IDw8ICJjaGVjayAyIiA8PCBlbmRsOwogICAgICAgICAgICAvL2NvdXQgPDwgInRyZWVbIjw8bm9kZTw8Il0gPSAiIDw8IHRyZWVbbm9kZV0gPDwgZW5kbDsKICAgICAgICAgICAgdHJlZVtub2RlXSArPSB2YWw7CiAgICAgICAgICAgICB0cmVlW25vZGVdICU9IE07CiAgICAgICAgICAgIC8vY291dCA8PCAidHJlZVsiPDxub2RlPDwiXSA9ICIgPDwgdHJlZVtub2RlXSA8PCBlbmRsOwoKICAgICAgICAgICAgaWYoYSE9YikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGF6eVsyKm5vZGUrMV0gKz0gdmFsOwogICAgICAgICAgICAgICAgbGF6eVsyKm5vZGUrMl0gKz0gdmFsOwogICAgICAgICAgICAgIC8vICBjb3V0IDw8ICJsYXp5WyI8PDIqbm9kZSsxPDwiXSA9ICIgPDwgbGF6eVtub2RlKjIrMV0gPDwgZW5kbDsKICAgICAgICAgICAgICAgIC8vY291dCA8PCAibGF6eVsiPDwyKm5vZGUrMjw8Il0gPSAiIDw8IGxhenlbbm9kZSoyKzJdIDw8IGVuZGw7CgogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIH0KICAgICAgICBpbnQgbWlkID0gKGErYikvMjsKICAgICAgICBxdWVyeV9hZGRfdXBkYXRlKG5vZGUqMisxLCBhLCBtaWQsIGksIGosIHZhbCk7CiAgICAgICAgcXVlcnlfYWRkX3VwZGF0ZShub2RlKjIrMiwgMSttaWQsIGIsIGksIGosIHZhbCk7CiAgICAgICAgdHJlZVtub2RlXSA9IHN1bSh0cmVlW25vZGUqMisxXSwgdHJlZVtub2RlKjIrMl0pOwogICAgfQoKICAgIHZvaWQgcXVlcnlfbXVsX3VwZGF0ZShpbnQgbm9kZSwgaW50IGEsIGludCBiLCBpbnQgaSwgaW50IGosIGludCB2YWwpCiAgICB7CiAgICAgICAgaWYobGF6eVtub2RlXSE9MCkKICAgICAgICB7CiAgICAgICAgICAgLy8gdHJlZVtub2RlXSAqPSBsYXp5W25vZGVdOwogICAgICAgICAgICAvL3RyZWVbbm9kZV0gJT0gTTsKCiAgICAgICAgICAgIGlmKGEhPWIpewogICAgICAgICAgICAgICAgbGF6eVsyKm5vZGUrMV0gKz0gbGF6eVtub2RlXTsKICAgICAgICAgICAgICAgIGxhenlbMipub2RlKzJdICs9IGxhenlbbm9kZV07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgbGF6eVtub2RlXSA9IDA7CiAgICAgICAgfQoKICAgICAgICBpZihhID4gYiB8fCBhID4gaiB8fCBiIDwgaSkKICAgICAgICAgICAgcmV0dXJuOwoKICAgICAgICBpZihhID49IGkgJiYgYiA8PSBqKQogICAgICAgIHsKICAgICAgICAgICAgdHJlZVtub2RlXSAqPSB2YWw7CiAgICAgICAgICAgIHRyZWVbbm9kZV0gJT0gTTsKCiAgICAgICAgICAgIGlmKGEhPWIpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGxhenlbbm9kZSoyKzFdICs9IHZhbDsKICAgICAgICAgICAgICAgIGxhenlbbm9kZSoyKzJdICs9IHZhbDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHJldHVybiA7CiAgICAgICAgfQoKICAgICAgICBxdWVyeV9tdWxfdXBkYXRlKG5vZGUqMisxLCBhLCAoYStiKS8yLCBpLCBqLCB2YWwpOwogICAgICAgIHF1ZXJ5X211bF91cGRhdGUobm9kZSoyKzIsIDErKGErYikvMiwgYiwgaSwgaiwgdmFsKTsKCiAgICAgICAgdHJlZVtub2RlXSA9IHN1bSh0cmVlW25vZGUqMisxXSwgdHJlZVtub2RlKjIrMl0pOwogICAgfQoKICAgIHZvaWQgcXVlcnlfc2V0dmFsdWUoaW50IG5vZGUsIGludCBhLCBpbnQgYiwgaW50IGksIGludCBqLCBpbnQgdmFsKQogICAgewogICAgICAgICBpZihsYXp5W25vZGVdICE9IDApCiAgICAgICAgewogICAgICAgIHRyZWVbbm9kZV0gKz0gbGF6eVtub2RlXTsKCgkJaWYoYSE9Yil7CiAgICAgICAgICAgIGxhenlbMipub2RlKzFdICs9IGxhenlbbm9kZV07CiAgICAgICAgICAgIGxhenlbMipub2RlKzJdICs9IGxhenlbbm9kZV07CgkJfQogICAgICAgICAgICBsYXp5W25vZGVdID0gMDsKICAgICAgICB9CgogICAgICAgIGlmKGEgPiBiIHx8IGEgPiBqIHx8IGIgPCBpKQogICAgICAgICAgICByZXR1cm47CgogICAgICAgIGlmKGEgPj0gaSAmJiBiIDw9IGopCiAgICAgICAgewogICAgICAgICAgICB0cmVlW25vZGVdID0gdmFsOwoKICAgICAgICAgICAgaWYoYSE9YikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgbGF6eVsyKm5vZGUrMV0gPSB2YWw7CiAgICAgICAgICAgICAgICBsYXp5WzIqbm9kZSsyXSA9IHZhbDsKICAgICAgICAgICAgfQogICAgICAgIGVsc2UKCSAgCXJldHVybiA7CgogICAgICAgIH0KCiAgICAgICAgcXVlcnlfc2V0dmFsdWUobm9kZSoyKzEsIGEsIChhK2IpLzIsIGksIGosIHZhbCk7CiAgICAgICAgcXVlcnlfc2V0dmFsdWUobm9kZSoyKzIsIDErKGErYikvMiwgYiwgaSwgaiwgdmFsKTsKCiAgICAgICAgdHJlZVtub2RlXSA9IHN1bSh0cmVlW25vZGUqMisxXSwgdHJlZVtub2RlKjIrMl0pOwogICAgfQoKICAgIC8vQWRkaXRpb25hbCBGdW5jdGlvbgogICAgdm9pZCBwcmludChpbnQgbm9kZSwgaW50IGEsIGludCBiKQogICAgewogICAgICAgIGlmKGE+YikKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIGlmKGE9PWIpewogICAgICAgICAgICBjb3V0IDw8IHRyZWVbbm9kZV0gPDwgIigiPDxub2RlPDwiKSI8PCIgIiA7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IG1pZCA9IChhK2IpLzI7CiAgICAgICAgcHJpbnQoMipub2RlKzEsYSxtaWQpOwogICAgICAgIHByaW50KDIqbm9kZSsyLG1pZCsxLGIpOwoKICAgIH0KCgp9Owp0ZW1wbGF0ZSA8Y2xhc3MgVD4KY2xhc3MgSW5wdXR7CgogICAgcHVibGljOgogICBUIHJlYWRfaW50KCkgewogICBjaGFyIGMgPSBnYygpOwogICB3aGlsZShjPCcwJyB8fCBjPic5JykKICAgIGMgPSBnYygpOwogICBUIHJldCA9IDA7CgogIHdoaWxlKGM+PScwJyAmJiBjPD0nOScpIHsKICAgIHJldCA9IDEwICogcmV0ICsgYyAtIDQ4OwogICAgYyA9IGdjKCk7CiAgICB9CiAgcmV0dXJuIHJldDsKfQp9OwoKaW50IG1haW4odm9pZCkKewogICAgSW5wdXQ8bGw+aXA7CiAgICBsbCBhbnMseCx5LCB2OwogICAgbGwgKmFyLCBhbnN3ZXI7CiAgICBsbCBuID0gaXAucmVhZF9pbnQoKTsKICAgIGxsIHEgPSBpcC5yZWFkX2ludCgpOwogICAgYXIgPSAobGwqKW1hbGxvYyhuKnNpemVvZihsbCkpOwogICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICAgICBhcltpXSA9IGlwLnJlYWRfaW50KCk7CgogICAgU2VnbWVudFRyZWU8bGw+IHN0KG4pOwogICAgc3QuYnVpbGRfdHJlZSgwLG4tMSwwLGFyKTsKCiAgICB3aGlsZShxLS0pCiAgICB7CiAgICAgICAgYW5zID0gaXAucmVhZF9pbnQoKTsKICAgICAgICB4ID0gaXAucmVhZF9pbnQoKTsKICAgICAgICB5ID0gaXAucmVhZF9pbnQoKTsKCiAgICAgICAgaWYoYW5zIT00KQogICAgICAgICAgICB2ID0gaXAucmVhZF9pbnQoKTsKCiAgICAgICAgeCAtPSAxOwogICAgICAgIHkgLT0gMTsKCiAgICAgICAgaWYoYW5zPT0xKQogICAgICAgICAgICBzdC5xdWVyeV9hZGRfdXBkYXRlKDAsMCxuLTEseCx5LHYpOwogICAgICAgIGlmKGFucz09MikKICAgICAgICAgICAgc3QucXVlcnlfbXVsX3VwZGF0ZSgwLDAsbi0xLHgseSx2KTsKICAgICAgICBpZihhbnM9PTMpCiAgICAgICAgICAgIHN0LnF1ZXJ5X3NldHZhbHVlKDAsMCxuLTEseCx5LHYpOwogICAgICAgIGlmKGFucz09NCl7CiAgICAgICAgICAgIGFuc3dlciA9IChsbClzdC5xdWVyeV9zdW0oMCwwLG4tMSx4LHkpOwogICAgICAgICAgICBjb3V0IDw8IGFuc3dlciA8PCBlbmRsOwogICAgICAgIH0KCiAgICAgICAvLyBzdC5wcmludCgwLDAsbi0xKTsKICAgICAgICAvL2NvdXQgPDwgZW5kbDsKCiAgICB9CgoKICAgIHJldHVybiAwOwp9Cg==