#include<cstdio>
#include<cmath>
#define NMAX 100001
using namespace std; 
long n,m,lim;
long a[NMAX];
long aib[NMAX];


long query (long ind) {
	long sum=0;
	while (ind) {
		sum=sum+aib[ind];
		ind=ind-(((ind^(ind-1))+1)>>1);
	}
	return sum;
}

void update (long val , long ind) {
	while (ind<=n) {
		aib[ind]=aib[ind]+val;
		ind=ind+(((ind^(ind-1))+1)>>1);
	}
}

long noname (long val) {
	long med,s=0,last=-1,st,dr;
	/*med=lim;
	while (med && med<=lim) {
		if (s+aib[med]<=val) {
			last=med;
			med=med/2;
			s=s+aib[med];
		}
		else
			med=med+(((med^(med-1))+1)>>1);
	}*/
	st=1;
	dr=lim;
	while (st<=dr) {
		med=(st+dr)/2;
		s=query(med);
		if (s<val)
			st=med+1;
		else {
			if (s==val)
				last=med;
			dr=med-1;
		}
	}
	return last;
}

void read () {
	long dubios,putere2;
	scanf("%ld%ld",&n,&m);
	dubios=log2(n);
	putere2=1<<dubios;
	if (putere2==n)
		lim=n;
	else
		lim=putere2*2;

	for (long i=1;i<=n;++i) {
		scanf("%ld",&a[i]);
		update(a[i],i);
	}
}

void solve () {
	long one,two,three;
	for (long j=0;j<m;j++) {
		scanf("%ld%ld",&one,&two);
		if (one==0) {
			scanf("%ld",&three);
			update (three,two);
		}
		if (one==1) {
			scanf("%ld",&three);
			printf ("%ld\n",query (three)-query(two-1));
		}
		if (one==2) {
			printf("%ld\n",noname(two));
		}
	}
}

int main () {
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	
	read();
	solve();
	return 0;
}