#include <fstream>

using namespace std;

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

int n,m,v[100005],op,a,b;
int p2[]={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824};

void update(int i, int x)
{
    int bn=0;
    while(i<=n)
    {
        v[i]+=x;
        while((i&p2[bn])==0) ++bn;
        i+=p2[bn];
        ++bn;
    }
}

int sum(int a, int b)
{
    int sa=0,sb=0,bn=0;
    while(b>0)
    {
        sb+=v[b];
        while((b&p2[bn])==0) ++bn;
        b-=p2[bn];
        ++bn;
    }
    --a;
    bn=0;
    while(a>0)
    {
        sa+=v[a];
        while((a&p2[bn])==0) ++bn;
        a-=p2[bn];
        ++bn;
    }
    return sb-sa;
}

int poz(int k)
{
    int i,step;
    for(step=1;step<n;step<<=1);
    for(i=0;step;step>>=1)
        if(i+step<=n)
            if(k>=v[i+step])
            {
                i+=step;
                k-=v[i];
                if(k==0) return i;
            }
    return -1;
    /*i=1;
    while(sum(1,i)!=k)
        if(i<n) ++i;
        else return -1;
    return i;*/
}

int main()
{
    int i;
    f>>n>>m;
    for(i=1;i<=n;++i)
    {
        f>>a;
        update(i,a);
    }
    //for(i=1;i<=n;++i) g<<v[i]<<' ';
    //g<<'\n';
    //for(i=1;i<=n;++i) g<<sum(i,i)<<' ';
    //g<<'\n';
    for(;m;--m)
    {
        f>>op;
        switch(op)
        {
            case 0: f>>a>>b; update(a,b); break;
            case 1: f>>a>>b; g<<sum(a,b)<<'\n'; break;
            case 2: f>>a; g<<poz(a)<<'\n'; break;
        }
    }
    f.close(); g.close();
    return 0;
}