#include <iostream>
#include<fstream>
#define NMAX 100001
using namespace std;
ofstream g("aib.out");
int n,a[NMAX];
void adauga(int x,int poz)
{
    int k,ci;
    while(poz<=n)
    {
        a[poz]+=x;
        ci=poz;
        k=0;
        while(ci%2==0)
        {
            k++;
            ci=ci/2;
        }
        poz=poz+(1<<k);
    }

}
int suma(int aa, int poz)
{
        int k,ci,s1=0,s2=0;
        while(poz>0)
        {
            s1+=a[poz];
            ci=poz;
            k=0;
            while(ci%2==0)
            {
                k++;
                ci=ci/2;
            }
            poz=poz-(1<<k);
        }
        poz=aa-1;
        while(poz>0)
        {
            s2+=a[poz];
            ci=poz;
            k=0;
            while(ci%2==0)
            {
                k++;
                ci=ci/2;
            }
            poz=poz-(1<<k);
        }
        return s1-s2;
}
int pozmin(int aa)
{
    int s=1,v=0;
    while(s<n)
        s=s<<1;
    while(s)
    {
        if(v+s<=n)
        {
            if(aa>=a[v+s])
            {
                v+=s;
                aa-=a[v];
                if(aa==0)
                    return v;
            }
        }
        s=s>>1;
    }
    return -1;
}
int main()
{
    ifstream f("aib.in");
    int m,cc,a,b;
    f>>n>>m;
    for(int i=1;i<=n;++i)
    {
        f>>cc;
        adauga(cc,i);
    }
    for(int i=1;i<=m;i++)
    {
        f>>cc;
        if(cc==0)
        {
            f>>a>>b;
            adauga(b,a);
        }
        if(cc==1)
        {
            f>>a>>b;
            g<<suma(a,b)<<"\n";
        }
        if(cc==2)
        {
            f>>a;
            g<<pozmin(a)<<"\n";
        }
    }
    f.close();
    g.close();
    return 0;
}