#include <stdio.h>
#define zeros(x) ((x ^ (x - 1)) & x)
#define MAX 100005

int cb(int x);
void Add(int x, int q);
int Compute(int x);

int n, m, v, AIB[MAX], i, a, b, ind;

int main(){
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++){
		scanf("%d", &v);
		Add(i, v);
	}

	for(i = 0; i < m; i++){
		scanf("%d", &ind);
		switch(ind){
			case 0:{
							 scanf("%d%d", &a, &b);
							 Add(a, b);
						 }; break;
			case 1:{
							 scanf("%d%d", &a, &b);
							 printf("%d\n", Compute(b) - Compute(a - 1));
						 }; break;
			default:{
								scanf("%d", &a);
								printf("%d\n", cb(a));
							}
		}
	}
	return 0;
}

void Add(int x, int q){
	int i;
	for(i = x; i <= n; i += zeros(i))
		AIB[i] += q;
}

int Compute(int x){
	int i, rez = 0;
	for(i = x; i > 0; i -= zeros(i))
		rez += AIB[i];
	return rez;
}

int cb(int x){
	int s = 1, d = n, mij;
	while(s < d){
		mij = (s + d) / 2;
		if(Compute(mij) == x)
			return mij;
		if(Compute(mij) > x)
			d = mij - 1;
		else
			s = mij + 1;
	}

	if(Compute(s) == x)
		return s;
	return -1;
}