#include <fstream>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n, m, i, j, x, y, k, a[100010], putere[10010], p, c, s, aux;

void Putere(){
    for(i=2; i<10001; i++)
        putere[i]=putere[i/2]+1;
}

void Querry(int x, int v){
    c=0;
    while(x<=n)
    {
        a[x]+=v;
        aux=( x^( x&(x-1) ) );
        c+=putere[aux];
        x+=aux;
        c+=1;
    }
}

int Sum(int x){
    c=s=0;
    while(x>0)
    {
        s+=a[x];
        aux=( x^( x&(x-1) ) );
        c+=putere[aux];
        x-=aux;
        c+=1;
    }
    return s;
}

int Search(int v){
    for(p=1; p<n; p<<=1);
    for(int i=0; p; p>>=1)
        if(i+p<=n)
            if(a[i+p]<=v)
            {
                i+=p;
                v-=a[i];
                if(!v)
                    return i;
            }
    return -1;
}

int main(){
    Putere();
    f>>n>>m;
    for(i=1; i<=n; i++)
    {
        f>>x;
        Querry(i, x);
    }
    for(i=1; i<=m; i++)
    {
        f>>k;
        if(k<2)
        {
            f>>x>>y;
            if(!k)
                Querry(x, y);
            else
                g<<Sum(y)-Sum(x-1)<<"\n";
        }
        else
        {
            f>>x;
            g<<Search(x)<<"\n";
        }
    }
    return 0;
}