#include <fstream>
#include <vector>
using namespace std;

vector<int> bit;
int maxVal;

void update(int x, int val){
    while(x<=maxVal){
        bit[x]+=val;
        x += x & -x;
    }
}

int get(int x){
    if(x==0||x>maxVal) return 0;
    else{
        int s=0;
        while(x){
            s+=bit[x];
            x -= x&-x;
        }
        return s;
    }
}

int poz(int x){
    int mask=1;
    while(mask<=maxVal) mask<<=1;
    mask>>=1;

    int y=x-1;
    int idx=0;

    for(;mask;mask>>=1)
        if(idx+mask<=maxVal){
            if(bit[idx+mask]<=y){
                y-=bit[idx+mask];
                idx+=mask;
            }
        }

    if(get(idx+1)==x) return idx+1;
    else return -1;
}

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

    int n,m; fin>>n>>m;
    maxVal=n;
    bit.resize(n+1,0);

    for(int i=1;i<=n;++i){
        int x; fin>>x;
        update(i,x);
    }

    for(int i=0;i<m;++i){
        int op,a,b; fin>>op;
        switch(op){
            case 0:
                fin>>a>>b;
                update(a,b);
                break;
            case 1:
                fin>>a>>b;
                fout<<get(b)-get(a-1)<<'\n';
                break;
            case 2:
                fin>>a;
                fout<<poz(a)<<'\n';
                break;
        }

    }

}