#include<iostream>
#include<fstream>
using namespace std;
int N,M,f[1000010],t[1000010];
int sum(int i){
	int s=0;
	while(i>0){
		s+=t[i];
		i-=(i&-i);
	}
	return s;
}
void upd(int i,int v){
	while(i<=N){
		t[i]+=v;
		i+=(i&-i);
	}
}
int main(){
	ifstream in("aib.in");
	ofstream out("aib.out");
	in>>N>>M;
	for(int i=1;i<=N;i++){
		in>>f[i];
		upd(i,f[i]);
	}
	while(M--){
		int w,a,b;
		in>>w;
		if(w==0){
			in>>a>>b;
			upd(a,b);
		}
		else if(w==1){
			in>>a>>b;
			out<<sum(b)-sum(a-1)<<'\n';
		}
		else if(w==2){
			in>>a;
			int l=1,r=N;
			bool done=false;
			while(l!=r){
				int m=(l+r)/2;
				int c=sum(m);
				if(c==a){
					out<<m<<'\n';
					done=true;
					break;
				}
				else if(c>a)r=m;
				else l=m+1;
			}
			if(!done)if(sum(r)==a)out<<r<<'\n';
		}
	}
	return 0;
}