#include <fstream>

using namespace std;

int aib[100005];
int n;

void update(int nod,int val)
{
    int ind;
    for(ind=nod;ind<=n;ind+=(ind&(-ind)))
       aib[ind]+=val;
}

int query(int nod)
{
   int sum=0;
   for(;nod>0;nod-=(nod&(-nod)))
       sum+=aib[nod];
   return sum;
}

int poz_min(int k)
{
   int st=1,dr=n,mijl=(n+1)>>1,aux;
   while(st<=dr)
   {
      aux=query(mijl);
      if(aux==k)
          return mijl;
      else if(aux<k)
          st=mijl+1;
      else
          dr=mijl-1;
      mijl=(st+dr)>>1;
   }
   return -1;
}

int main()
{
    ifstream cin("aib.in");
    ofstream cout("aib.out");

    int m=0,i,t,cod,a,b;
    cin>>n>>m;

    for(i=0;i<n;i++)
    {
       cin>>t;
       update(i+1,t);
    }

    for(i=0;i<m;i++)
    {
       cin>>cod>>a;
       if(cod!=2)
          cin>>b;
       if(!cod)
          update(a,b);
       else if(cod==1)
          cout<<query(b)-query(a-1)<<'\n';
       else
          //cout<<"-1\n";
          cout<<poz_min(a)<<'\n';
    }
    cin.close();
    cout.close();
    return 0;
}