#include<fstream>
#define zeros(x) ( (x ^ (x - 1)) & x )
#define dim 150007
using namespace std;
int V[dim],AIB[dim],n,m,i,op,a,b;
ifstream in("aib.in");
ofstream out("aib.out");
void add (int x,int quantity){
	
	for(int i=x;i<=n;i+=zeros(i))
		AIB[i]+=quantity;
	
}

int compute(int x ) {
	
	int sum=0;
	int i;
	for( i=x; i>0 ;i-=zeros(i))
		sum+=AIB[i];
	
	return sum;
}
int bs(int a){
	
	int p,u,mid;
	p=1,u=n;
	
	while(p<=u){
		mid=p+(u-p)/2;
		if(compute(mid)>a)
			u=mid-1;
		else{
			if(compute(mid)==a)
				return mid;
			else
				p=mid+1;
		}
	}
	return -1;
}
int main () {
	
	in>>n>>m;
	
	for(int i=1; i<=n ;i++ ) {
		in>>V[i];
		add(i,V[i]);
	}
	
	for(int i=1; i<=m; ++i) {
		
		in>>op;
		
		if(op==0){
			
			in>>a>>b;
			
			add(a,b);
			
		}
		else {
			
			if(op==1){
				in>>a>>b;
				
				out<<compute(b)-compute(a-1)<<"\n";
				
			}
			else{
				in>>a;
				out<<bs(a)<<"\n";
			}
		}
		
	}
	return 0;
}