#include<fstream>
using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");
const int Nmax = 100002;
int A[Nmax];
int N,M;
int lsb(int &x){
    return ( x & (-x) );
}
int query(int x){
    int sum=0;
    while(x>0){
        sum+=A[x];
        x-=lsb(x);
    }
    return sum;
}
void update(int x,int val){
    while(x<=N){
        A[x]+=val;
        x+=lsb(x);
    }
}
int kquery(int a){
    int sum=0,ans=0,x=N;
    while(x>0){
        if( sum + A[x] <= a ){
            ans+=x;
            sum+=A[x];
        }
        x>>=1;
    }
    if(sum==a) return ans;
    return -1;
}
int main(){
    in>>N>>M;
    for(int i=1;i<=N;i++){
        int x;
        in>>x;
        update(i,x);
    }
    for(int i=1;i<=M;i++){
        int c,a,b;
        in>>c;
        if(c==0){
            in>>a>>b;
            update(a,b);
        }
        if(c==1){
            in>>a>>b;
            out<<query(b)-query(a-1)<<'\n';
        }
        if(c==2){
            in>>a;
            out<<kquery(a)<<'\n';
        }
    }
    return 0;
}