#include <stdio.h>
#define N_MAX 100010
int V[N_MAX];
int logn, n, m;
inline int calc(int x) {
	return x^(x&(x-1));
}
void aib_update(int x, int poz) {
	for(int i = poz; i <= n; i += calc(i)) {
		V[i] += x;
	}
}
int aib_query(int poz) {
	int s = 0;
	for(int i = poz; i > 0; i -= calc(i)) {
		s += V[i];
	}
	return s;
}
void spQuery(int sum) {
	int poz = 0, s = 0;
	for(int i = logn; i >= 0; i--) {
		if(poz + (1<<i) <= n && V[poz+(1<<i)] + s < sum) {
			poz += (1<<i);
			s += V[poz];
		}
	}
	poz++;
	if(poz > n || aib_query(poz) != sum) {
		printf("-1\n");
	}
	else {
		printf("%d\n", poz);
	}
	
}
int main() {
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	
	for(logn = 0; (1<<logn) <= n; logn++);
	logn--;
	for(int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		aib_update(x,i);
	}
	for(int i = 1; i <= m; i++) {
		int op, a, b;
		scanf("%d", &op);
		if(op == 0) {
			scanf("%d%d", &a, &b);
			aib_update(b, a);
		}
		else if(op == 1) {
			scanf("%d%d", &a, &b);
			printf("%d\n",aib_query(b) - aib_query(a-1));
		}
		else {
			scanf("%d", &a);
			spQuery(a);
		}
	}
	return 0;
}