#include <fstream>

using namespace std;

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

int v[100010],i,x,y,n,p,u,mij,op,k,q;

int lsb (int i){
    return i&(-i);
}

void update (int poz, int x) {

    for ( int i=poz; i<=n;i+=lsb(i))
        v[i]+=x;
}

int query (int poz){

    int sum=0;
    for (int i=poz;i!=0;i-=lsb(i))
        sum+=v[i];

    return sum;
}

int cautb (int k) {

    p=1;u=n;
    while (p<=u) {
        mij=(p+u)/2;
        if (query(mij)<k)
            p=mij+1;
        else
            u=mij-1;
    }
    if (query (p)!=k)
        return -1;
    return p;
}


int main () {

    fin>>n>>q;
    for (i=1;i<=n;i++){
        fin>>x;
        update (i,x);
    }
    while (q--) {
        fin>>op;
        if (op==0) {
            fin>>x>>y;
            update(x,y);
        }else
            if (op==1) {
                fin>>x>>y;
                fout<<query (y) - query (x-1)<<"\n";
            }else {
                fin>>k;
                fout<<cautb(k)<<"\n";
            }
    }


    return 0;
}