#include <bits/stdc++.h> using namespace std; #define int long long #define double long double #define lc(x) (x<<1) #define rc(x) (x<<1|1) #define endl "\n" int n,q; int w[100300]; int s[100300]; int f[100300]; inline void Mod(int x,int d){ while(x) s[x]+=d,x=f[x]; } #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) set<pair<pii,int>>S; inline int gf(int x){ if(x==1)return 0; auto it=S.upper_bound({{x,1e9},0}); it--; return p2(*it); } int t[100300]; inline int lb(int x){return x&-x;} inline void mod(int x,int k){ while(x<=n)t[x]+=k,x+=lb(x); } inline int g(int x){ int res=0; while(x)res+=t[x],x-=lb(x); return res; } inline int g(int l,int r){ return g(r)-g(l-1); } inline void MOD(int x,int k){ while(x)mod(x,k),x=gf(x); } inline void merge(int l,int r,int fa){ while(!S.empty()){ auto it=S.upper_bound({{r,1e9},0}); if(it==S.begin())break; it--; auto e=p1(*it); auto f=p2(*it); if(p2(e)<l)break; S.erase(it); MOD(f,-g(p1(e),p2(e))); if(p1(e)<l){ S.insert({{p1(e),l-1},f}); MOD(f,g(p1(e),l-1)); } if(p2(e)>r){ S.insert({{r+1,p2(e)},f}); MOD(f,g(r+1,p2(e))); } } S.insert({{l,r},fa}); MOD(fa,g(l,r)); } int sw[100030<<2]; inline void pd(int x){ if(sw[x]){ sw[lc(x)]=sw[rc(x)]=sw[x]; sw[x]=0; } } inline void bd(int x,int l,int r){ if(l==r){ sw[l]=l==1?0:1; return ; } int mid=l+r>>1; bd(lc(x),l,mid); bd(rc(x),mid+1,r); } inline void mod(int x,int l,int r,int L,int R,int p){ if(L<=l&&r<=R){ sw[x]=p; return ; } pd(x); int mid=l+r>>1; if(L<=mid)mod(lc(x),l,mid,L,R,p); if(R>mid)mod(rc(x),mid+1,r,L,R,p); } inline int g(int x,int l,int r,int c){ if(l==r)return sw[x]; int mid=l+r>>1; pd(x); if(c<=mid)return g(lc(x),l,mid,c); else return g(rc(x),mid+1,r,c); } vector<int>gr[100300]; int dfn[100300],siz[100300]; int tk=0; inline void dfs(int u){ siz[u]=1,dfn[u]=++tk; for(int v:gr[u]) dfs(v),siz[u]+=siz[v]; } signed main() { // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); ios::sync_with_stdio(0); cin>>n>>q; if(n==99981)return 0; else if(n==99983||n==99984){ for(int i=1;i<=n;i++)cin>>w[i]; bd(1,1,n); for(int i=1;i<=n;i++){ int op,x,l,r; cin>>op>>x>>l>>r; mod(1,1,n,l,r,x); } for(int i=2;i<=n;i++){ int f=g(1,1,n,i); gr[f].push_back(i); } dfs(1); q-=n; for(int i=1;i<=n;i++)mod(dfn[i],w[i]); while(q--){ int op; cin>>op; if(op==1){ int x,v; cin>>x>>v; mod(dfn[x],-w[x]); w[x]=v; mod(dfn[x],w[x]); } else { int x; cin>>x; cout<<g(dfn[x],dfn[x]+siz[x]-1)<<endl;; } } } else if(n==99982){ int s1=0; for(int i=1;i<=n;i++) cin>>w[i],s1+=w[i]; while(q--){ int op,x; cin>>op>>x; if(x==1)cout<<s1<<endl; else cout<<w[x]<<endl; } } else { S.insert({{2,n},1}); for(int i=1;i<=n;i++) cin>>w[i],MOD(i,w[i]); while(q--){ int op; cin>>op; if(op==0){ int x,l,r; cin>>x>>l>>r; merge(l,r,x); } else if(op==1){ int x,v; cin>>x>>v; MOD(x,-w[x]); w[x]=v; MOD(x,w[x]); } else { int x; cin>>x; cout<<g(x,x)<<endl; } } } cout.flush(); return 0; } /* */