/*
author: kartik8800
*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr(a,b) for(ll i = a; i < b; i++)
#define mod 1000000007
#define inf (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x
#define triplet pair<ll,pair<ll,ll>>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
struct node
{
ll sum;
ll setAll;
ll increment;
bool setAllValid;
node()
{
sum = 0;
setAllValid = 0;
increment = 0;
}
void Reset()
{
setAllValid = increment = 0;
}
};
class segtree
{
int range;
vector<node> tree;
public:
void build(vector<int>& v)
{
range = v.size();
tree.assign(4*range, node());
build_recur(v, 0, range-1, 0);
}
void build_recur(vector<int>& v, int l, int r, int node_no)
{
if(l == r){
if(l < v.size())
tree[node_no].sum = v[l];
else tree[node_no].sum = 0;
return;
}
int mid = (l+r)/2;
build_recur(v, l, mid, 2*node_no + 1);
build_recur(v, mid + 1, r, 2*node_no + 2);
tree[node_no].sum = tree[2*node_no + 1].sum + tree[2*node_no + 2].sum;
}
ll range_query(int L, int R)
{
return range_query_recur(0, 0, range - 1, L, R);
}
void incUpdate_recur(int node, int l, int r, int& L, int& R, int& X)
{
if(r < L || R < l || l >= range)
return;
if(L <= l && R >= r)
{
tree[node].increment += X;
return;
}
applyAggr(node,l,r);
int mid = (l+r)/2;
incUpdate_recur(2*node+1,l,mid,L,R,X);
incUpdate_recur(2*node+2,mid+1,r,L,R,X);
applyAggr(2*node+1, l, mid);
applyAggr(2*node+2, mid+1, r);
tree[node].sum = tree[2*node+1].sum + tree[2*node+2].sum;
}
void incUpdate(int L, int R, int X)
{
incUpdate_recur(0,0,range-1,L,R,X);
}
void setUpdate_recur(int node, int l, int r, int& L, int& R, int& X)
{
if(r < L || R < l || l >= range)
return;
if(L <= l && R >= r)
{
tree[node].setAllValid = 1;
tree[node].setAll = X;
tree[node].increment = 0;
return;
}
applyAggr(node,l,r);
int mid = (l+r)/2;
setUpdate_recur(2*node+1,l,mid,L,R,X);
setUpdate_recur(2*node+2,mid+1,r,L,R,X);
applyAggr(2*node+1, l, mid);
applyAggr(2*node+2, mid+1, r);
tree[node].sum = tree[2*node+1].sum + tree[2*node+2].sum;
}
void setUpdate(int L, int R, int X)
{
setUpdate_recur(0,0,range-1,L,R,X);
}
void compose(int par, int child)
{
if(tree[par].setAllValid){
tree[child].setAllValid = 1;
tree[child].setAll = tree[par].setAll;
tree[child].increment = tree[par].increment;
}
else tree[child].increment += tree[par].increment;
}
void applyAggr(int node, int l, int r)
{
if(tree[node].setAllValid)
tree[node].sum = (r-l+1)*tree[node].setAll;
tree[node].sum += (r-l+1)*tree[node].increment;
if(l != r){
compose(node, 2*node + 1);
compose(node, 2*node + 2);
}
tree[node].Reset();
}
ll range_query_recur(int node, int l, int r, int& L, int& R)
{
if(r < L || R < l || l >= range)
return 0;
applyAggr(node, l, r);
if(L <= l && R >= r)
return tree[node].sum;
int mid = (l+r)/2;
return range_query_recur(2*node + 1, l, mid, L, R) + range_query_recur(2*node + 2, mid+1, r, L, R);
}
};
int main() {
fast_io;
int n,q;
cin >> n >> q;
vector<int> v(n);
for(int i = 0; i < n; i++)
cin >> v[i];
segtree sg;
sg.build(v);
while(q--)
{
int t;
cin >> t;
if(t == 1){
int a,b,x;
cin >> a >> b >> x;
sg.incUpdate(a-1,b-1,x);
}
else if(t == 2){
int a,b,x;
cin >> a >> b >> x;
sg.setUpdate(a-1,b-1,x);
}
else {
int a,b;
cin >> a >> b;
cout << sg.range_query(a-1,b-1) <<'\n';
}
}
return 0;
}
LyoKICAgIGF1dGhvcjoga2FydGlrODgwMAoqLwojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGZyKGEsYikgZm9yKGxsIGkgPSBhOyBpIDwgYjsgaSsrKQojZGVmaW5lIG1vZCAxMDAwMDAwMDA3CiNkZWZpbmUgaW5mICgxTEw8PDYwKQojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwgKHgpLmVuZCgpCiNkZWZpbmUgcHJEb3VibGUoeCkgY291dCA8PCBmaXhlZCA8PCBzZXRwcmVjaXNpb24oMTApIDw8IHgKI2RlZmluZSB0cmlwbGV0IHBhaXI8bGwscGFpcjxsbCxsbD4+CiNkZWZpbmUgZmFzdF9pbyBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKE5VTEwpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpzdHJ1Y3Qgbm9kZQp7CiAgICBsbCBzdW07CiAgICBsbCBzZXRBbGw7CiAgICBsbCBpbmNyZW1lbnQ7CiAgICBib29sIHNldEFsbFZhbGlkOwogICAgbm9kZSgpCiAgICB7CiAgICAgICBzdW0gPSAwOwogICAgICAgc2V0QWxsVmFsaWQgPSAwOwogICAgICAgaW5jcmVtZW50ID0gMDsKICAgIH0KICAgIHZvaWQgUmVzZXQoKQogICAgewogICAgICAgc2V0QWxsVmFsaWQgPSBpbmNyZW1lbnQgPSAwOwogICAgfQp9OwoKY2xhc3Mgc2VndHJlZQp7CiAgICBpbnQgcmFuZ2U7CiAgICB2ZWN0b3I8bm9kZT4gdHJlZTsKcHVibGljOgogICAgdm9pZCBidWlsZCh2ZWN0b3I8aW50PiYgdikKICAgIHsKICAgICAgICByYW5nZSA9IHYuc2l6ZSgpOwogICAgICAgIHRyZWUuYXNzaWduKDQqcmFuZ2UsIG5vZGUoKSk7CiAgICAgICAgYnVpbGRfcmVjdXIodiwgMCwgcmFuZ2UtMSwgMCk7CiAgICB9CiAgICB2b2lkIGJ1aWxkX3JlY3VyKHZlY3RvcjxpbnQ+JiB2LCBpbnQgbCwgaW50IHIsIGludCBub2RlX25vKQogICAgewogICAgICAgIGlmKGwgPT0gcil7CiAgICAgICAgICAgIGlmKGwgPCB2LnNpemUoKSkKICAgICAgICAgICAgICAgIHRyZWVbbm9kZV9ub10uc3VtID0gdltsXTsKICAgICAgICAgICAgZWxzZSB0cmVlW25vZGVfbm9dLnN1bSA9IDA7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgaW50IG1pZCA9IChsK3IpLzI7CiAgICAgICAgYnVpbGRfcmVjdXIodiwgbCwgbWlkLCAyKm5vZGVfbm8gKyAxKTsKICAgICAgICBidWlsZF9yZWN1cih2LCBtaWQgKyAxLCByLCAyKm5vZGVfbm8gKyAyKTsKICAgICAgICB0cmVlW25vZGVfbm9dLnN1bSA9IHRyZWVbMipub2RlX25vICsgMV0uc3VtICsgdHJlZVsyKm5vZGVfbm8gKyAyXS5zdW07CiAgICB9CiAgICBsbCByYW5nZV9xdWVyeShpbnQgTCwgaW50IFIpCiAgICB7CiAgICAgICAgcmV0dXJuIHJhbmdlX3F1ZXJ5X3JlY3VyKDAsIDAsIHJhbmdlIC0gMSwgTCwgUik7CiAgICB9CgogICAgdm9pZCBpbmNVcGRhdGVfcmVjdXIoaW50IG5vZGUsIGludCBsLCBpbnQgciwgaW50JiBMLCBpbnQmIFIsIGludCYgWCkKICAgIHsKICAgICAgICBpZihyIDwgTCB8fCBSIDwgbCB8fCBsID49IHJhbmdlKQogICAgICAgICAgICByZXR1cm47CiAgICAgICAgaWYoTCA8PSBsICYmIFIgPj0gcikKICAgICAgICB7CiAgICAgICAgICAgIHRyZWVbbm9kZV0uaW5jcmVtZW50ICs9IFg7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgYXBwbHlBZ2dyKG5vZGUsbCxyKTsKICAgICAgICBpbnQgbWlkID0gKGwrcikvMjsKICAgICAgICBpbmNVcGRhdGVfcmVjdXIoMipub2RlKzEsbCxtaWQsTCxSLFgpOwogICAgICAgIGluY1VwZGF0ZV9yZWN1cigyKm5vZGUrMixtaWQrMSxyLEwsUixYKTsKICAgICAgICBhcHBseUFnZ3IoMipub2RlKzEsIGwsIG1pZCk7CiAgICAgICAgYXBwbHlBZ2dyKDIqbm9kZSsyLCBtaWQrMSwgcik7CiAgICAgICAgdHJlZVtub2RlXS5zdW0gPSB0cmVlWzIqbm9kZSsxXS5zdW0gKyB0cmVlWzIqbm9kZSsyXS5zdW07CiAgICB9CgogICAgdm9pZCBpbmNVcGRhdGUoaW50IEwsIGludCBSLCBpbnQgWCkKICAgIHsKICAgICAgICBpbmNVcGRhdGVfcmVjdXIoMCwwLHJhbmdlLTEsTCxSLFgpOwogICAgfQoKICAgIHZvaWQgc2V0VXBkYXRlX3JlY3VyKGludCBub2RlLCBpbnQgbCwgaW50IHIsIGludCYgTCwgaW50JiBSLCBpbnQmIFgpCiAgICB7CiAgICAgICAgaWYociA8IEwgfHwgUiA8IGwgfHwgbCA+PSByYW5nZSkKICAgICAgICAgICAgcmV0dXJuOwogICAgICAgIGlmKEwgPD0gbCAmJiBSID49IHIpCiAgICAgICAgewogICAgICAgICAgICB0cmVlW25vZGVdLnNldEFsbFZhbGlkID0gMTsKICAgICAgICAgICAgdHJlZVtub2RlXS5zZXRBbGwgPSBYOwogICAgICAgICAgICB0cmVlW25vZGVdLmluY3JlbWVudCA9IDA7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICAgICAgYXBwbHlBZ2dyKG5vZGUsbCxyKTsKICAgICAgICBpbnQgbWlkID0gKGwrcikvMjsKICAgICAgICBzZXRVcGRhdGVfcmVjdXIoMipub2RlKzEsbCxtaWQsTCxSLFgpOwogICAgICAgIHNldFVwZGF0ZV9yZWN1cigyKm5vZGUrMixtaWQrMSxyLEwsUixYKTsKICAgICAgICBhcHBseUFnZ3IoMipub2RlKzEsIGwsIG1pZCk7CiAgICAgICAgYXBwbHlBZ2dyKDIqbm9kZSsyLCBtaWQrMSwgcik7CiAgICAgICAgdHJlZVtub2RlXS5zdW0gPSB0cmVlWzIqbm9kZSsxXS5zdW0gKyB0cmVlWzIqbm9kZSsyXS5zdW07CiAgICB9CgogICAgdm9pZCBzZXRVcGRhdGUoaW50IEwsIGludCBSLCBpbnQgWCkKICAgIHsKICAgICAgICBzZXRVcGRhdGVfcmVjdXIoMCwwLHJhbmdlLTEsTCxSLFgpOwogICAgfQoKICAgIHZvaWQgY29tcG9zZShpbnQgcGFyLCBpbnQgY2hpbGQpCiAgICB7CiAgICAgICAgaWYodHJlZVtwYXJdLnNldEFsbFZhbGlkKXsKICAgICAgICAgICAgdHJlZVtjaGlsZF0uc2V0QWxsVmFsaWQgPSAxOwogICAgICAgICAgICB0cmVlW2NoaWxkXS5zZXRBbGwgPSB0cmVlW3Bhcl0uc2V0QWxsOwogICAgICAgICAgICB0cmVlW2NoaWxkXS5pbmNyZW1lbnQgPSB0cmVlW3Bhcl0uaW5jcmVtZW50OwogICAgICAgIH0KICAgICAgICBlbHNlIHRyZWVbY2hpbGRdLmluY3JlbWVudCArPSB0cmVlW3Bhcl0uaW5jcmVtZW50OwogICAgfQoKICAgIHZvaWQgYXBwbHlBZ2dyKGludCBub2RlLCBpbnQgbCwgaW50IHIpCiAgICB7CiAgICAgICAgaWYodHJlZVtub2RlXS5zZXRBbGxWYWxpZCkKICAgICAgICAgICAgdHJlZVtub2RlXS5zdW0gPSAoci1sKzEpKnRyZWVbbm9kZV0uc2V0QWxsOwoKICAgICAgICB0cmVlW25vZGVdLnN1bSArPSAoci1sKzEpKnRyZWVbbm9kZV0uaW5jcmVtZW50OwoKICAgICAgICBpZihsICE9IHIpewogICAgICAgICAgICBjb21wb3NlKG5vZGUsIDIqbm9kZSArIDEpOwogICAgICAgICAgICBjb21wb3NlKG5vZGUsIDIqbm9kZSArIDIpOwogICAgICAgIH0KCiAgICAgICAgdHJlZVtub2RlXS5SZXNldCgpOwogICAgfQoKICAgIGxsIHJhbmdlX3F1ZXJ5X3JlY3VyKGludCBub2RlLCBpbnQgbCwgaW50IHIsIGludCYgTCwgaW50JiBSKQogICAgewogICAgICAgIGlmKHIgPCBMIHx8IFIgPCBsIHx8IGwgPj0gcmFuZ2UpCiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIGFwcGx5QWdncihub2RlLCBsLCByKTsKICAgICAgICBpZihMIDw9IGwgJiYgUiA+PSByKQogICAgICAgICAgICByZXR1cm4gdHJlZVtub2RlXS5zdW07CiAgICAgICAgaW50IG1pZCA9IChsK3IpLzI7CiAgICAgICAgcmV0dXJuIHJhbmdlX3F1ZXJ5X3JlY3VyKDIqbm9kZSArIDEsIGwsIG1pZCwgTCwgUikgKyByYW5nZV9xdWVyeV9yZWN1cigyKm5vZGUgKyAyLCBtaWQrMSwgciwgTCwgUik7CiAgICB9Cn07CgppbnQgbWFpbigpIHsKICAgZmFzdF9pbzsKICAgaW50IG4scTsKICAgY2luID4+IG4gPj4gcTsKCiAgIHZlY3RvcjxpbnQ+IHYobik7CiAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgY2luID4+IHZbaV07CgogICBzZWd0cmVlIHNnOwogICBzZy5idWlsZCh2KTsKCiAgIHdoaWxlKHEtLSkKICAgewogICAgICAgIGludCB0OwogICAgICAgIGNpbiA+PiB0OwogICAgICAgIGlmKHQgPT0gMSl7CiAgICAgICAgICAgIGludCBhLGIseDsKICAgICAgICAgICAgY2luID4+IGEgPj4gYiA+PiB4OwogICAgICAgICAgICBzZy5pbmNVcGRhdGUoYS0xLGItMSx4KTsKICAgICAgICB9CiAgICAgICAgZWxzZSBpZih0ID09IDIpewogICAgICAgICAgICBpbnQgYSxiLHg7CiAgICAgICAgICAgIGNpbiA+PiBhID4+IGIgPj4geDsKICAgICAgICAgICAgc2cuc2V0VXBkYXRlKGEtMSxiLTEseCk7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBpbnQgYSxiOwogICAgICAgICAgICBjaW4gPj4gYSA+PiBiOwogICAgICAgICAgICBjb3V0IDw8IHNnLnJhbmdlX3F1ZXJ5KGEtMSxiLTEpIDw8J1xuJzsKICAgICAgICB9CiAgIH0KICAgcmV0dXJuIDA7Cn0K