#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,aib[100005];
int UB (int x)
{return x&(-x);
}
void add(int i,int x)
{int j;
    for(j=i;j<=n;j+=UB(j))
      aib[j]+=x;
}
int sum(int x)
{int i,S;
S=0;
    for(i=x;i>0;i-=UB(i))
    S+=aib[i];
    return S;

}
int m,j,t,suma,x,u,a,b,st,dr,mij,i;
int main()
{
 f>>n>>m;
   for(i=1;i<=n;i++)
   {f>>x;
    add(i,x);
    }
    for(i=1;i<=m;i++)
       {f>>u;suma=0;
           if(u==0){
            f>>a>>b;
            add(a,b);
           }
           if(u==1)
           {f>>a>>b;
               suma-=sum(a-1);
               suma+=sum(b);
               g<<suma<<'\n';
           }
           if(u==2)
           {f>>x;

               st=1; dr=n;
               while(st<=dr)
              {mij=(st+dr)/2;
              t=sum(mij);
              if(t>x)dr=mij-1;
        else if(t<x)st=mij+1;
        else if(t==x){g<<mij<<'\n'; break;}
        else if(st==dr && t!=x){g<<-1<<'\n';
        break;}
              }

           }


       }
    return 0;
}