#include <fstream>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
#define zeros(x) ((x) & (-x))

int AIB[100010],N,M;
void add(int x,int pos){
	for(pos; pos<=N;pos+=zeros(pos) ){
		AIB[pos]+=x;
	}
}

int query(int a, int b){
	int sum = 0;
	for(b; b > 0;b -= zeros(b)){
		sum+=AIB[b];	
	}
	a--;
	for(a; a > 0;a -= zeros(a)){
		sum-=AIB[a];
	}
	return sum;
}

int search(int val){
	int i, step,tmp;
    for (step = 1; step <= N; step <<= 1);
    step <<=1;
    for (i = 0; step; step >>= 1){
        if ((i + step <= N) && query(1,i + step) <= val){
           i += step;
       }
   }
   tmp = query(1,i);
   if(tmp != val) return -1;
   while(query(1,i-1) == tmp && i > 1) i--; 
   return i;
}
int main(){
	int key,x,y;
	fin >> N >> M;
	for(int i = 1;i <= N;i++){
		fin >> key;
		add(key,i);
	}
	for(int j = 0;j < M;j++){
		fin >> key;
		if(key == 0){
			fin >> x >> y;
			add(y,x);
		}else
		if(key == 1){
			fin >> x >> y;
			fout << query(x,y) << '\n';
		}else{
			fin >> x;
			fout << search(x) << '\n';
		}
	}
	return 0;
}