#include <stdio.h>

#define MAXN 100001

// cate elemente insumeaza aib[x] ( aib[x] = sum v[i] cu i= x-sumed(x)+1 : x )
// = 2 la nr de zerouri terminale
#define sumed(x) ((x^(x-1))&x)

int N,M;
int digN=1;
int v[MAXN];
int aib[MAXN];

// v[x] este incrementat cu val
void add(int x, int val)
{
	for(;x<=N;x+=sumed(x))
		aib[x] += val;
}

// intoarce sum v[i] cu i = 1 : x
int get(int x)
{
	int sum = 0;
	for(;x>0;x-=sumed(x))
		sum += aib[x];
	return sum;
}

int position(int sum)
{
	int pos = 0;
	int i = digN;
	
	while( i != 0){
		int mid = pos + i;
		if( mid <= N ){		
			if( aib[mid] == sum ){
				return mid;
			}
			else if( aib[mid] < sum ){
				pos = mid;
				sum = sum - aib[mid];
			}
		}
		i = i>>1;
	}
	return -1;
}

int main(int argc, char* argv[])
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	
	scanf("%d %d",&N,&M);
	
	int i,a,b,op;
	
	i=N;
	while(i!=1){
		digN = digN << 1;
		i = i >> 1;
	}
	
	for(i=1;i<=N;i++){
		scanf("%d",&a);
		add(i,a);
	}
	
	for(i=1;i<=M;i++){
		scanf("%d",&op);
		switch(op){
			case 0:
				scanf("%d %d",&a,&b);
				add(a,b);
				break;
			case 1:
				scanf("%d %d",&a,&b);
				if( a == 1 )
					printf("%d\n",get(b));
				else
					printf("%d\n",get(b)-get(a-1));
				break;
			case 2:
				scanf("%d",&a);
				printf("%d\n",position(a));
				break;			
		}
	}
	
	return 0;
}