如题

/*
*/
#include<bits/stdc++.h>
#define rep(i,s1,s2,s3) for(i = s1;i <= s2;i += s3)
#define r(i,s1,s2,s3) for(i = s1;i >= s2;i -= s3)
#define sort stable_sort
#define ull unsigned ll
#define INF 0x7f7f7f7f
#define ll long long
using namespace std;
ll n,m,d,a[2000010];
struct tree{
	struct node{
		ll tag,size,value;
	}t[2000010 * 4 + 1];
	void renew(ll l,ll r,ll id,ll data){
		t[id].tag += data; t[id].value += data * t[id].size;
	}
	void push_down(ll l,ll r,ll id){
		if(!t[id].tag) return ;
		ll mid = (l + r) >> 1;
		renew(l,mid,id << 1,t[id].tag);
		renew(mid + 1,r,id << 1 | 1,t[id].tag);
		t[id].tag = 0;
	}
	void push_up(ll id){
		t[id].value = t[id << 1 | 1].value + t[id << 1].value;
	}
	void build(ll id,ll dep,ll i,ll b[]){
		if(dep == d){
			t[id].value = b[i];
			t[id].size = i <= n;
			return ;
		}
		build(id << 1,dep + 1,i,b);
		build(id << 1 | 1,dep + 1,i + (1 << dep),b);
		push_up(id);
		t[id].size = t[id << 1 | 1].size + t[id << 1].size;
	}
	void update(ll l,ll r,ll id,ll data,ll x,ll s){
		if(!x){if(!s) renew(l,r,id,data); return ;}
		push_down(l,r,id);
		ll mid = l + r >> 1;
		if(!(s & 1)) update(l,mid,id << 1,data,x - 1,s >> 1);
		else update(mid + 1,r,id << 1 | 1,data,x - 1,s >> 1);
		push_up(id);
		return ;
	}
	ll query(ll l,ll r,ll id,ll x,ll s){
		if(!x) return t[id].value * (!s);
		push_down(l,r,id);
		ll res = 0,mid = (l + r) >> 1;
		if(!(s & 1)) res += query(l,mid,id << 1,x - 1,s >> 1);
		else res += query(mid + 1,r,id << 1 | 1,x - 1,s >> 1);
		push_up(id);
		return res;
	}
}t;
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>m;
	ll i,x = 1,y,w,op,last = 0;
	d = ceil(log2(n));
	rep(i,1,n,1) cin>>a[i];
	t.build(1,0,1,a);
	rep(i,1,m,1){
		cin>>op;
		op = ((last + op) & 1) + 1;
		if(op == 1){
			cin>>x>>y>>w;
			x = min(x,d);
			y %= (1 << x);
			if(y > 0) t.update(1,n,1,w,x,y - 1);
			else t.update(1,n,1,w,x,(1 << x) - 1);
		}else{
			cin>>x>>y;
			x = min(x,d);
			y %= (1 << x);
			if(y > 0) cout<<(last = t.query(1,n,1,x,y - 1))<<'\n';
			else cout<<(last = t.query(1,n,1,x,(1 << x) - 1))<<'\n';
		}
	}
	return 0;
}