#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#define MAXN 100010
#define zeros(x) (((x)^((x)-1))&(x))
using namespace std;

int AIB[MAXN],N,M;

inline void add(int x,int y) {
	int i;
	for (i=x;i<=N;i+=zeros(i)) {
		AIB[i] += y;
	}
}

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

inline int sum(int a,int b) {	
	return calc(b) - calc(a - 1);
}

inline int search(int x) {
	int i,step;
	for (step=1;step<N;step<<=1);
	for (i=0;step;step>>=1) {
		if (i + step <= N) {
			if (x >= AIB[i + step]) {
				i+=step;
				x-=AIB[i];
				if (!x) return i;
			}
		}
	}
	return -1;
}

int main() {

	ios::sync_with_stdio(false);

	memset(AIB,0,sizeof(AIB));
	
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	
	scanf("%d%d",&N,&M);
	
	int i,a,b,c;
	
	for (i=1;i<=N;++i) {scanf("%d",&a);add(i,a);}
	
	for (i=1;i<=M;++i) {
		
		scanf("%d",&c);
		if (c < 2) scanf("%d%d",&a,&b);
			  else scanf("%d",&a);
			  
		switch (c) {
			case 0:
				add(a,b);
				break;
			case 1:
				printf("%d\n",sum(a,b));
				break;
			case 2: 
				printf("%d\n",search(a));
				// TODO : implement binsearch here
				break;
			default:break;
		}
	}
	
	fclose(stdin);
	fclose(stdout);

	return 0;
}