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

using namespace std;

int AIB[100001], N, M;

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

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

int find(int a){    
	int st = 1;    
	int dr = N;     
	while(st <= dr)    {        
		int mij = (st + dr)/2;        
		int aux = Compute(mij);         
		if(aux == a)            
			return mij;         
		if(aux < a)            
			st = mij + 1;        
		else            
			dr = mij - 1;    
	}     
	return -1;
}

int main() {
	freopen ("aib.in", "r", stdin);
	freopen ("aib.out", "w", stdout);
	int i, opt, a, b, x;
	scanf ("%d %d", &N, &M);
	for (i = 1; i <= N; ++i) {
		scanf ("%d", &x);
		Add(i, x);
	}
	for (i = 1; i <= M; ++i) {
		scanf ("%d", &opt);
		if (opt == 0) {
			scanf ("%d %d", &a, &b);
			Add (a, b);
		}
		if (opt == 1) {
			scanf ("%d %d", &a, &b);
			printf ("%d\n", Compute(b) - Compute(a-1));
		}
		if (opt == 2) {
			scanf ("%d", &a);
			printf ("%d\n", find(a));
		}
	}
	return 0;
}