#include<iostream> using namespace std; inline int read(){ int i=getchar(),r=0; while(i<'0'||i>'9')i=getchar(); while(i>='0'&&i<='9')r=(r<<1)+(r<<3)+(i^48),i=getchar(); return r; } const int N=200100; int n,m,a[N]; void init(){ cin>>n>>m; for(int i=1;i<=n;i++)a[i]=read(); } namespace sub2{ int main(){ int sum=0; for(int i=1;i<=n;i++)sum+=a[i]; while(m--){ int opt=read(),x=read(); if(x==1)cout<<sum<<endl; else cout<<a[x]<<endl; } return 0; } } namespace sub3{ int rt,ls[N<<1],rs[N<<1],L[N<<1],R[N<<1],laz[N<<1],val[N<<1],ver; inline int New(int L_,int R_,int ls_,int rs_){ L[++ver]=L_,R[ver]=R_,ls[ver]=ls_,rs[ver]=rs_; return ver; } inline void push_down(int nd){ if(laz[nd]){ val[nd]=laz[nd]; laz[ls[nd]]=laz[rs[nd]]=laz[nd]; laz[nd]=0; } } int build(int l,int r){ if(l==r)return New(l,r,0,0); int mid=(l+r)>>1; return New(l,r,build(l,mid),build(mid+1,r)); } void modify(int l,int r,int x,int nd=rt){ push_down(nd); if(l<=L[nd]&&R[nd]<=r){laz[nd]=x;return;} if(l<=R[ls[nd]])modify(l,r,x,ls[nd]); if(r>=L[rs[nd]])modify(l,r,x,rs[nd]); } int get_val(int pos,int nd=rt){ push_down(nd); if(L[nd]==R[nd])return val[nd]; if(pos<=R[ls[nd]])return get_val(pos,ls[nd]); else get_val(pos,rs[nd]); } int t[N]; inline void add(int i,int k){while(i<=n)t[i]+=k,i+=i&-i;} inline int get_sum(int i){int r=0;while(i)r+=t[i],i-=i&-i;return r;} int fa[N],son[N],bro[N]; int siz[N],dfn[N]; void dfs(int nd){ siz[nd]=1,dfn[nd]=++*dfn; for(int i=son[nd];i;i=bro[i])dfs(i),siz[nd]+=siz[i]; } int main(){ rt=build(1,n); laz[rt]=1; for(int i=1;i<=n;i++){ int opt=read(),x=read(),l=read(),r=read(); modify(l,r,x); } for(int i=2;i<=n;i++){ fa[i]=get_val(i); bro[i]=son[fa[i]]; son[fa[i]]=i; } dfs(1); for(int i=1;i<=n;i++)add(dfn[i],a[i]); for(int i=n+1;i<=m;i++){ int opt=read(),x=read(); if(opt==1){ add(dfn[x],-a[x]); a[x]=read(); add(dfn[x],a[i]); } else{ printf("%lld\n",get_sum(dfn[x]+siz[x]-1)-get_sum(dfn[x]-1)); } } return 0; } } namespace sub4{ int sum[N],fa[N]; inline void add(int x,int k){ while(x!=1){ x=fa[x]; sum[x]+=k; } } int main(){ sum[1]=a[1]; for(int i=2;i<=n;i++)sum[i]=a[i],sum[1]+=sum[i],fa[i]=1; while(m--){ int opt=read(),x=read(); if(opt==0){ int l=read(),r=read(); add(l,-sum[l]); fa[l]=x; add(l,sum[l]); } else if(opt==1){ int v=read(); add(x,v-a[x]); sum[x]+=v-a[x]; a[x]=v; } else printf("%lld\n",sum[x]); } return 0; } } namespace sub5{ int rt,ls[N<<1],rs[N<<1],L[N<<1],R[N<<1],laz[N<<1],val[N<<1],ver; inline int New(int L_,int R_,int ls_,int rs_){ L[++ver]=L_,R[ver]=R_,ls[ver]=ls_,rs[ver]=rs_; return ver; } inline void push_down(int nd){ if(laz[nd]){ val[nd]=laz[nd]; laz[ls[nd]]=laz[rs[nd]]=laz[nd]; laz[nd]=0; } } int build(int l,int r){ if(l==r)return New(l,r,0,0); int mid=(l+r)>>1; return New(l,r,build(l,mid),build(mid+1,r)); } void modify(int l,int r,int x,int nd=rt){ push_down(nd); if(l<=L[nd]&&R[nd]<=r){laz[nd]=x;return;} if(l<=R[ls[nd]])modify(l,r,x,ls[nd]); if(r>=L[rs[nd]])modify(l,r,x,rs[nd]); } int get_val(int pos,int nd=rt){ push_down(nd); if(L[nd]==R[nd])return val[nd]; if(pos<=R[ls[nd]])return get_val(pos,ls[nd]); else get_val(pos,rs[nd]); } int sum[N],fa[N]; inline void add(int x,int k){ while(x!=1){ x=get_val(x); sum[x]+=k; } } int main(){ rt=build(1,n); laz[rt]=1; sum[1]=a[1]; for(int i=2;i<=n;i++)sum[i]=a[i],sum[1]+=sum[i],fa[i]=1; while(m--){ int opt=read(),x=read(); if(opt==0){ int l=read(),r=read(); modify(l,r,x); } else if(opt==1){ int v=read(); add(x,v-a[x]); sum[x]+=v-a[x]; a[x]=v; } else printf("%lld\n",sum[x]); } return 0; } } signed main(){ init(); if(n==99981){return 0;} if(n==99982){sub2::main();return 0;} if(99983<=n&&n<=99984){sub3::main();return 0;} if(99985<=n&&n<=99988){sub4::main();return 0;} return 0; }