#include <iostream>
#include <fstream>

using namespace std;

#define zeros(x) ((-x)&(x))

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

int n,qs;
int AIB[100005];

void add(int x, int val){
    for(int i=x;i<=n;i+=zeros(i))
        AIB[i]+=val;
}
int query(int x){
    int s=0;
    for(int i=x;i>=1;i-=zeros(i))
        s+=AIB[i];
    return s;
}
int query_int(int x, int y){
    return query(y)-query(x-1);
}
int query_smin(int x){
    int st=1,dr=n,mij,sol=-1;
    while(st<=dr){
        mij=(st+dr)/2;
        int q=query(mij);
        if(q>=x){
            dr=mij-1;
            if(q==x)sol=mij;
        }
        else st=mij+1;
    }
    return sol;
}
void read(){
    in>>n>>qs;
    for(int i=1,x;i<=n;i++){
        in>>x;
        add(i,x);
    }
}
void queries(){
    for(int i=1,op,x,y;i<=qs;i++){
        in>>op;
        if(op==0){
            in>>x>>y;
            add(x,y);
        }
        else if(op==1){
            in>>x>>y;
            out<<query_int(x,y)<<"\n";
        }
        else if(op==2){
            in>>x;
            out<<query_smin(x)<<"\n";
        }
    }
}
int main(){
    read();
    queries();
    return 0;
}