#include <stdio.h>
#include <stdlib.h>
using namespace std;


int N, M;
int *aib;

int cool(int x){
	return x & (x - 1) ^ x;
}

void update(int index, int value){
	for (int i = index; i <= N + 1; i += cool(i))
		aib[i] += value;
}

int query(int index){
	int sum = 0;
	for (int i = index; i > 0; i -= cool(i))
		sum += aib[i];
	return sum;	
}

int search(int value){
	int step;
	for (step = 1; step < N + 1; step <<= 1);
	for (int i = 0; step >= 0; step >>= 1){
		if (aib[i + step] <= value && i + step <= N ){
			i += step;
			value -= aib[i];
			if (!value) return i;
		}
	}
	return -1;
}


int main(){
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);
	
	scanf("%d %d", &N, &M);
	aib = (int*) calloc(N + 1, sizeof(int));

	for (int i = 1, x; i < N + 1; ++i){
		scanf("%d", &x);
		update(i, x);
	}
	
	for (int i = 0, cod, a, b; i < M; ++i){
		scanf("%d", &cod);
		switch (cod){
			case 0: {
					scanf("%d %d", &a , &b); 	
					update(a,b);
					break;
				}
			case 1: {
					scanf("%d %d", &a , &b); 	
					printf("%d\n", query(b) - query(a - 1));
					break;
				}
			case 2: {
					scanf("%d", &a);
					printf("%d\n", search(a));
					break;
				}
		}
	}


	fclose(stdout);
	fclose(stdin);

	return 0;
}