#include<stdio.h>

const int Nmax = 100001;

int A[Nmax], N, M;

int lsb(int i) {
	return i ^ (i & (i - 1));
} // cel mai nesemnificativ bit de 1 al lui i

void update(int poz, int val) {
	int i;
	for(i=poz; i<=N; i+=lsb(i))
		A[i]+=val;
}

int query(int poz) {
	int sum=0, i;
	for(i=poz; i>0; i-=lsb(i))
		sum+=A[i];
	return sum;
}

int search(int st, int dr, int val) {
	if(st>dr)
		return -1;
	int mij=(st+dr)/2;
	int aux=query(mij);
	if(aux==val)
		return mij;
	if(aux<val)
		return search(mij+1,dr,val);
	return search(st,mij-1,val);
}

int main() {
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	
	int i, val, poz, tip, st, dr, sum, sol;
	
	scanf("%d %d",&N,&M);
	for(i=1; i<=N; i++) {
		scanf("%d",&val);
		update(i,val);
	}
	
	for(; M; --M) {
		scanf("%d",&tip);
		switch(tip) {
			case 0:
				scanf("%d %d",&poz,&val);
				update(poz,val);
				break;
			case 1:
				scanf("%d %d",&st,&dr);
				sum=query(dr)-query(st-1);
				printf("%d\n",sum);
				break;
			case 2:
				scanf("%d",&val);
				sol=search(1,N,val);
				printf("%d\n",sol);
				break;
		}
	}
	
	return 0;
}