#include<iostream>
#include<fstream>

#define form ((p^(p-1))&p)

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int n,m,a[100001];

void modificare(int p,int x){
    while(p<=n){
        a[p]+=x;
        p+=form;
    }
}

int suma(int p){
    int s=0;
    while(p>0){
        s+=a[p];
        p-=form;
    }
    return s;
}

int minim(int x){
    int step;
    for(step=1;step<n;step<<=1);
        for(int i=0;step;step>>=1)
            if(i+step<=n){
                if(x>=a[i+step]){
                     x-=a[i+step];
                    i+=step;
                    if(x==0)
                        return i;
                }
            }
    return -1;
}

void citire(){
    fin>>n>>m;
    int x;
    for(int i=1;i<=n;i++){
        fin>>x;
        modificare(i,x);
    }
    for(int i=0;i<m;i++){
        int tip,x,y;
        fin>>tip;
        if(tip==0){
            fin>>x>>y;
            modificare(x,y);
        }
      else
        if(tip==1){
            fin>>x>>y;
            fout<<suma(y)-suma(x-1)<<"\n";
        }
       else{
            fin>>x;
           fout<<minim(x)<<"\n";
        }
    }
}

int main(){
    citire();
    fin.close();
    fout.close();
    return 0;
}