#include <stdio.h>
#include <stdlib.h>
#define N 100100
#define st stderr
int aib[N];
int n,m;
inline int nr_zero_term(int x){
	int k=0;
	while ((x^0)!=0 && !(x&1)){
		++k;
		x>>=1;
	}
	return k;
}
void update(int a,int b){
	int x=nr_zero_term(a),now;
	aib[a]+=b;
	now=a+(1<<x);
	while (now<=n){
		aib[now]+=b;
		x=nr_zero_term(now);
		now+=(1<<x);
	}
}
int query(int b){
	int x,S=0;
	while (b>0){
		S+=aib[b];
		x=nr_zero_term(b);
		b-=(1<<x);
	}
	return S;
}
int search(int a){
	int i,step;
	for (step=1;step<n;step<<=1);
	for (i=0;step;step>>=1)
		if (i+step<=n){
			if( a >= aib[i+step] ){  
                i += step, a -= aib[i];  
                if ( !a)
					return i;  
            }  
		}
	return -1;
}
int main(void){
	int i,a,b,x;
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;++i){
		scanf("%d",&x);
		update(i,x);
	}
	while (m--){
		scanf("%d%d",&x,&a);
		if (x==0){
			scanf("%d",&b);
			update(a,b);
		}
		else
			if (x==1){
				scanf("%d",&b);
				printf("%d\n",query(b)-query(a-1));
			}
			else
				printf("%d\n",search(a));
	}
}