#include <fstream>
#define bit(i) ((i^(i-1))&i)
#define dim 100001
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int i,n,m,poz,val,k,sol[dim],v[dim];
void upDate(int poz, int val)
{
    for(int i=poz;i<=n;i+=bit(i))
        sol[i]+=val;
}
int query(int poz)
{
    int ret=0;
    for(int i=poz;i>0;i-=bit(i))
        ret+=sol[i];
    return ret;
}
int search(int val)
{
    int st=1;
    int dr=n;
    int mijl;
    int cand;
    int ret=-1;
    while(st<=dr)
    {
        mijl=st+(dr-st)/2;
        cand=query(mijl);
        if(cand<val)
            st=mijl+1;
        else
        {
            dr=mijl-1;
            if(cand==val)
                ret=mijl;
        }
    }
    return ret;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>val;
        upDate(i,val);
    }
    for(i=1;i<=m;i++)
    {
        fin>>k>>poz;
        if(k==0)
        {
            fin>>val;
            upDate(poz,val);
            continue;
        }
        if(k==1)
        {
            fin>>val;
            fout<<query(val)-query(poz-1)<<'\n';
            continue;
        }
        if(k==2)
            fout<<search(poz)<<'\n';
    }
    return 0;
}