#include<stdio.h>

#define NMAX 100001

int aib[NMAX];
int N , M;

void update(int n , int val);
int query(int n);
int search(int x);

int main()
{
	int t,x,y;
	freopen("aib.in" , "r" , stdin );
	freopen("aib.out" , "w" , stdout );

	scanf("%d%d" , &N , &M );
	for(int i = 1 ; i <= N ; ++i ){
		scanf("%d" , &t);
		update(i,t);
	}

	for(int i = 1 ; i <= M ; ++i ){
		scanf("%d" , &t );
		if(t == 0){
			scanf("%d%d" , &x , &y );
			update(x,y);
		}
		else
			if(t == 1){
				scanf("%d%d" ,&x , &y );
				printf("%d\n" , query(y)-query(x-1));
			}
			else{
				scanf("%d" , &x);
				printf("%d\n" , search(x));
			}
	}
	return 0;
}

void update(int n , int val)
{
	while(n <= N){
		aib[n] += val;
		n = 2*n-(n&(n-1));
	}
}

int query(int x)
{
	int s = 0;
	while(x){
		s+=aib[x];
		x = x&(x-1);
	}
	return s;
}

int search(int x)
{
	int ls , ld , m;
	ls = 1 , ld = N;
	while(ls <= ld) {
		m = (ls+ld)/2;
		int sum = query(m);
		if(sum == x)return m;
		if(sum < x)
			ls = m+1;
		else ld = m-1;
	}
	return -1;
}