#include <fstream>

using namespace std;

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

int v[100010],n,lg;

int indexbin (int n)
{
    return n&(-n);
}
void update (int pos , int val)
{
    if(pos>n)
        return;
    v[pos]+=val;
    pos+=indexbin(pos);
    update ( pos , val);
}

int query(int a)
{
    int s=0;
    for(int i=a;i>=1;i-=i&(-i)) s+=v[i];
    return s;
}

int binsearch(int target)
{
    int x=0;
    for(int i=lg;i>=0;i--)
        if(x+(1<<i)<=n and v[x+(1<<i)]<target)
        {
            x+=1<<i;
            target-=v[x];
        }
    return x+1;
}

int main()
{int m,a,b,q;
    f>>n>>m;
    for(lg=1;(1<<lg)<=n;++lg);--lg;
    for(int i=1;i<=n;++i)
    {
        f>>a;
        update(i,a);
    }
    for(int i=1;i<=m;i++)
    {
        f>>q;
        if(!q)
        {
            f>>a>>b;
            update(a,b);
        }
        else if(q==1)
        {
            f>>a>>b;
            t<<query(b)-query(a-1)<<'\n';
        }
        else
        {
            f>>a;
            int k=binsearch(a);
            if(query(k)==a) t<<k<<'\n';
            else t<<-1<<'\n';
        }
    }
    return 0;
}