#include <fstream>

using namespace std;
unsigned int aib[100001], n, m, a, b, c;
void update(int poz, int val)
{
    int c=0;
    while(poz<=n)
    {
        aib[poz]+=val;
        while(!(poz & (1<<c)))
            c++;
        poz+=(1<<c);
        c++;
    }
}
int query(int poz)
{
    int c=0;
    int s=0;
    while(poz>0)
    {
        s=s+aib[poz];
        while(!(poz & (1<<c)))
            c++;
        poz-=(1<<c);
        c++;
    }
    return s;
}
int crr(int val)
{
    int p, i;
    p=(1<<(n-1));
    for(i=0; p>0; p/=2)
    {
        if(i+p<=n)
        {
            if(val>=aib[i+p])
            {
                val-=aib[i+p];
                i+=p;
                if(val==0)
                    return i;
            }
        }
    }
    return -1;
}
int main()
{
    int i;
    ifstream f("aib.in");
    ofstream g("aib.out");
    f>>n>>m;
    for(i=1; i<=n; i++)
    {
        f>>a;
        update(i, a);
    }
    for(i=1; i<=m; i++)
    {
        f>>a;
        if(a==0)
        {
            f>>b>>c;
            update(b, c);
        }
        if(a==1)
        {
            f>>b>>c;
            g<<query(c)-query(b-1)<<"\n";
        }
        if(a==2)
        {
            f>>b;
            g<<crr(b)<<"\n";
        }
    }

}