#include <fstream>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int arbib[100005],tip,n,m,i,v[100005],pozitie,valoare,unu,doi,poz,a;
void update(int x,int y)
{int i;
    for (i=x;i<=n;i+=(i&(-i)))
    {
        arbib[i]+=y;
    }
}
int sum(int x)
{
    int reel=0;
    for (int i=x;i>=1;i-=(i&(-i)))
    {
        reel+=arbib[i];
    }
    return reel;
}
int main()
{
   fin>>n>>m;
   for (i=1;i<=n;i++)
   {
       fin>>v[i];
       update(i,v[i]);
   }
   for (i=1;i<=m;i++)
   {
       fin>>tip;
       if (tip==0)
       {
           fin>>pozitie>>valoare;
           update(pozitie,valoare);
       }
       else if (tip==1)
       {
           fin>>unu>>doi;
           fout<<sum(doi)-sum(unu-1)<<'\n';
       }
       else
       {
           fin>>a;
           int s=0,poz=0;
           for (int b=17;b>=0;b--)
           {
               if (poz+(1<<b)<=n&&s+arbib[poz+(1<<b)]<a)
               {
                   s+=arbib[poz+(1<<b)];
                   poz+=(1<<b);
               }
           }
           if (poz+1>n||sum(poz+1)!=a)
           {
               fout<<-1<<'\n';
           }
           else fout<<poz+1<<'\n';
       }
   }
    return 0;
}