#include <fstream>

using namespace std;
ifstream in ("aib.in");
ofstream out ("aib.out");
int aib[100003],n;
int lsb (int x)
{
  return x&-x;
}
int update (int poz, int a)
{
    for(;poz<=n;poz+=lsb(poz))
      aib[poz]+=a;
}
int quary (int poz)
{
    int ans=0;
    for(;poz>0;poz-=lsb(poz))
      ans+=aib[poz];
    return ans;
}
int main()
{
    int m,a,b,c,i,msk,ans,k;
    in>>n>>m;
    for(i=1;i<=n;i++)
    {
        in>>a;
        update(i,a);
    }
    for(i=1;i<=m;i++)
    {
        in>>c;
        if(c==0)
        {
            in>>a>>b;
            update(a,b);
        }
        else
        if(c==1)
        {
            in>>a>>b;
            out<<quary(b)-quary(a-1)<<'\n';
        }
        else
        {
            in>>k;
            ans=0;
            for(msk=1<<20;msk>0;msk/=2)
                if(ans+msk<=n&&k-aib[ans+msk]>=0)
                {
                    k-=aib[ans+msk];
                    ans+=msk;
                }
          if(k==0)
          out<<ans<<'\n';
          else
          out<<-1<<'\n';
        }
    }
    return 0;
}