#include <bits/stdc++.h>
#define DMAX 100010

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int AIB[DMAX];
int n,m;

void Add(int x,int quantity);
int Query(int x);
int searchv(int val);

int main()
{int i,val,x,y;
 fin>>n>>m;
 for(i=1;i<=n;i++)
     {fin>>val;
      Add(i,val);
     }
 for(i=1;i<=m;i++)
     {fin>>val>>x;
      if(val<2)
         fin>>y;
      if(!val)
         Add(x,y);
         else
         if(val==1)
            fout<<Query(y)-Query(x-1)<<'\n';
         else
         fout<<searchv(x)<<'\n';
     }
 return 0;
}
void Add(int x,int quantity)
{int i;
 for(i=x;i<=n;i+= ((i) & (-i)))
     AIB[i]+=quantity;
}
int Query(int x)
{int i,ret=0;
 for(i=x;i>0;i-= ((i) & (-i)))
     ret+=AIB[i];
 return ret;
}
int searchv(int val)
{int st=0,dr=n+1,mij;
 while(dr-st>1)
       {mij=(st+dr)/2;
        if(Query(mij)<val)
           st=mij;
           else
           dr=mij;
       }
 if(Query(dr) == val)
    return dr;
    else
    return -1;
}