constexpr int N=5e5+10;

struct node{
	int p,v;
	char op;
};node opt[N>>2],a[N>>2];

int n,m,cnt,q;
int ans[N>>2];

void CDQ(int l,int r){
	if(l==r){
		return ;
	}
	int mid=(l+r)>>1;
	CDQ(l,mid);
	CDQ(mid+1,r);
	int p=mid+1,sum=0,tot=l-1;
	rep(i,l,mid,1){
		while(p<=r && opt[i].p>opt[p].p){
			a[++tot]=opt[p];
			if(opt[p].op==2){
				ans[opt[p].v]+=sum;
			}
			if(opt[p].op==3){
				ans[opt[p].v]-=sum;
			}
			p++;
		}
		if(opt[i].op==1){
			sum+=opt[i].v;
		}
		a[++tot]=opt[i];
	}
	while(p<=r){
		a[++tot]=opt[p];
		if(opt[p].op==2){
			ans[opt[p].v]+=sum;
		}
		if(opt[p].op==3){
			ans[opt[p].v]-=sum;
		}
		p++;
	}
	memcpy(opt+l,a+l,sizeof (node)*(r-l+1));
}

void solve(){
	n=Read<int>(),m=Read<int>();
	rep(i,1,n,1){
		opt[++cnt]=(node){i,Read<int>(),1};
	}
	rep(i,1,m,1){
		int o=Read<int>();
		if(o==1){
			int x=Read<int>();
			opt[++cnt]=(node){x,Read<int>(),1};
		}
		else{
			opt[++cnt]=(node){Read<int>()-1,++q,3};
			opt[++cnt]=(node){Read<int>(),q,2};
		}
	}
	CDQ(1,cnt);
	rep(i,1,q,1){
		Write(ans[i],'\n');
	}
}