#include <bits/stdc++.h>
#define MAX (int)(1e5+5)
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int n,q,Arb[MAX];

void read();
void solve();
int lbs(int);
int caut_binar(int);
int Sum(int);
void Update(int,int);

int main(){
    read();
    solve();
    return 0;
}
int lbs(int x){
    return x&(-x);
}
int caut_binar(int x){
    int st=0,dr=n+1,mij,val;

    while(dr-st>1){
        mij=(st+dr)>>1;

        val=Sum(mij);
        if(val==x)
            return mij;

        if(val>x)
            dr=mij;
        else
            st=mij;
    }
    return -1;
}
int Sum(int x){
    int S=0;
    for(;x;x-=lbs(x))
        S+=Arb[x];
    return S;
}
void Update(int poz, int val){
    int i;
    for(i=poz;i<=n;i+=lbs(i)){
        Arb[i]+=val;
    }
}
void solve(){
    int task,a,b;
    while(q--){
        fin>>task;
        switch(task){
            case 0:
                fin>>a>>b;
                Update(a,b);
                break;
            case 1:
                fin>>a>>b;
                fout<<Sum(b)-Sum(a-1)<<'\n';
                break;
            case 2:
                fin>>a;
                fout<<caut_binar(a)<<'\n';
                break;
        }
    }
}
void read(){
    int i,x;
    fin>>n>>q;
    for(i=1;i<=n;++i){
        fin>>x;
        Update(i,x);
    }
}