#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n,m,d[100010],cod,aux;
void upd(int poz,int val)
{
    while(poz<=n)
    {
        d[poz]+=val;
        poz=poz+(poz&(-poz));
    }

}
int que(int poz2)
{
    int s=0;
    while(poz2>0)
    {
        s=s+d[poz2];
        poz2=poz2-(poz2&(-poz2));
    }
    return s;
}
int rez(int s)
{
    int l=aux,baza=0;

    while(s!=0&&l!=0)
    {
        if(s>=d[baza+l])
        {
            baza=baza+l;
            s=s-d[baza];
            l=l/2;
            while(baza+l>n)
            {
                l=l/2;
            }
        }
        else
        {
            l=l/2;
        }
    }

    if(s==0)
        return baza;
    else
        return -1;
}
int main()
{
    int val,poz1,poz2,i,s,poz;
    fin>>n>>m;
    poz=1;
    while(poz<=n)
    {
        aux=poz;
        poz=poz+(poz&(-poz));
    }
    for(i=1; i<=n; i++)
    {
        fin>>val;
        upd(i,val);
    }
    for(i=1; i<=m; i++)
    {
        fin>>cod;
        if(cod==0)
        {
            fin>>poz1>>val;
            upd(poz1,val);
        }
        else
        {
            if(cod==1)
            {
                fin>>poz1>>poz2;
                fout<<que(poz2)-que(poz1-1)<<'\n';
            }
            else
            {

                fin>>s;
                fout<<rez(s)<<'\n';

            }
        }
    }
}