#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--; 
   if(i == 0) i = -1;
   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';
        }
    }
    fout << '\n';
    return 0;
}