#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define pi pair<int,int> #define m_p make_pair #define p1 first #define p2 second using namespace std; typedef long long ll; const int maxn=1e6+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } namespace qwq { int t[maxn],fa[maxn],f[maxn],FA[maxn],dep[maxn],sum[maxn],tag[maxn]; int res[maxn]; int len,bel[maxn]; int n,q,w[maxn]; set<pair<pi,int> >st; void upd(int x,int w){ for(;x;){ res[x]+=w; int nw=x; if(FA[bel[x]])sum[bel[x]]+=w,x=FA[bel[x]]; else sum[bel[x]]+=w*dep[x],tag[x]+=w,x=f[x]; if(nw==n)break; } } void bd(int x){ int l=(x-1)*len+1,r=min(x*len,n); up(i,l,r)f[i]=fa[i]; down(i,r,l){ if(fa[i]<=r)f[i]=f[fa[i]],dep[i]=dep[fa[i]]+1; else dep[i]=1; } } void pd(int x){ int l=(x-1)*len+1,r=min(x*len,n); up(i,l,r){ if(fa[i]<=r)tag[fa[i]]+=tag[i],res[fa[i]]+=tag[i]; tag[i]=0; } if(FA[x]){ up(i,l,r)fa[i]=f[i]=FA[x],dep[i]=1;FA[x]=0; } } int qry(int l,int r){ int s=0; if(bel[l]==bel[r]){ pd(bel[l]);up(i,l,r)s+=res[i]; return s; }pd(bel[l]),pd(bel[r]); up(i,l,bel[l]*len)s+=res[i]; up(i,bel[l]+1,bel[r]-1)s+=sum[i]; up(i,(bel[r]-1)*len+1,r)s+=res[i]; return s; } int getfa(int x){ auto it=st.lower_bound(m_p(m_p(x,int(1e9)),int(1e9)));it--; return (*it).p2; } void UPD(int l,int r,int f){ vector<pair<pi,int> >DEL,INS; auto it=st.lower_bound(m_p(m_p(l,int(1e9)),int(1e9)));it--; if((*it).p1.p2>=r){ int g=qry(l,r); upd((*it).p2,-g); upd(f,g); if((*it).p1.p1<l)st.insert(m_p(m_p((*it).p1.p1,l-1),(*it).p2)); if((*it).p1.p2>r)st.insert(m_p(m_p(r+1,(*it).p1.p2),(*it).p2)); st.erase(it); st.insert(m_p(m_p(l,r),f)); return; }int g=qry(l,(*it).p1.p2); upd((*it).p2,-g),upd(f,g); if((*it).p1.p1<l)INS.p_b(m_p(m_p((*it).p1.p1,l-1),(*it).p2)); DEL.p_b(*it); while(1){ ++it; if((*it).p1.p2>=r){ int g=qry((*it).p1.p1,r); upd((*it).p2,-g),upd(f,g); DEL.p_b((*it)); if((*it).p1.p2>r)INS.p_b(m_p(m_p(r+1,(*it).p1.p2),(*it).p2)); break; } DEL.p_b(*it); int g=qry((*it).p1.p1,(*it).p1.p2); upd((*it).p2,-g);upd(f,g); } for(auto it:DEL)st.erase(it); for(auto it:INS)st.insert(it); st.insert(m_p(m_p(l,r),f)); } void slv(){ n=read(),q=read();up(i,1,n)res[n-i+1]=w[n-i+1]=read(); up(i,1,n-1)res[n]+=w[i];up(i,1,n)fa[i]=n;fa[n]=n+1;bel[n+1]=bel[n]+1; len=sqrt(n);up(i,1,n)bel[i]=(i-1)/len+1;up(i,1,bel[n])bd(i); up(i,1,n)sum[bel[i]]+=res[i]; st.insert(m_p(m_p(1,n-1),n)); while(q--){ int op=read(); if(!op){ int x=n-read()+1,l=n-read()+1,r=n-read()+1;swap(l,r); UPD(l,r,x); if(bel[l]==bel[r]){ pd(bel[l]); up(i,l,r)fa[i]=x; bd(bel[l]); } else { pd(bel[l]),pd(bel[r]); up(i,l,bel[l]*len)fa[i]=x;bd(bel[l]); up(i,bel[l]+1,bel[r]-1)FA[i]=x; up(i,(bel[r]-1)*len+1,r)fa[i]=x;bd(bel[r]); } }else if(op==1){ int x=n-read()+1,y=read(); upd(x,y-w[x]),w[x]=y; }else { int x=n-read()+1; printf("%lld\n",qry(x,x)); } } } } void slv(){ qwq::slv(); }int main(){ // freopen("tree.in","r",stdin); // freopen("tree.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }