#include <fstream>
#include <vector>

using namespace std;

ifstream cin("aib.in");
ofstream cout("aib.out");

long long n,m,t,a,b,i,k;
vector<long long>x;

void update (long long i, long long e)  ///i-index; e-ertek
{
    while(i<=n)
    {
        x[i]+=e;
        i+= (i & (-i));
    }
}

long long osszeg (long long i)
{
    long long r=0;

    while(i>0)
    {
        r+=x[i];
        i-=(i & (-i));
    }

    return r;
}

long long keres (long long a)
{
    int e=0, v=k, poz;
    while(v!=0)
    {
        poz=e+v;
        v>>=1;

        if(poz<=n)
        {
            if(a==x[poz]) return poz;
            else if(a>x[poz])
            {
                a-=x[poz];
                e=poz;
            }
        }
    }

    if(e!=0) return -1;
}

int main()
{
    cin>>n>>m;

    k=n;
    while(k!=(k & (-k))) k-=(k & (-k));

    x.resize(n+1);
    for(i=1;i<=n;++i)
    {
        cin>>a;
        update (i,a);
    }

    while(m)
    {
        cin>>t;
        if(t==0)
        {
            cin>>a>>b;
            update(a,b);
        }
        else
        if(t==1)
        {
            cin>>a>>b;
            cout<<osszeg(b)-osszeg(a-1)<<"\n";
        }
        else
        {
            cin>>a;
            cout<<keres(a)<<"\n";
            //cout<<"\n";
        }
        --m;
    }

    return 0;
}