#include <fstream>
#define NM 100003
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,i,a,b,s,val,c,x;
int v[NM];
void add(int x,int y){
   while(x<=n){
      v[x]+=y; x+=(0-x)&x;
   }
}
int sum(int x){
 s=0;
  while(x>=1){
    s+=v[x]; x-=(0-x)&x;
  }
  return s;
}
int cautbin(int val){
   int mijl,st,dr;
   st=1; dr=n;
   while(st<=dr){
     mijl=(st+dr)/2;
     s=sum(mijl);
     if(s<val) st=mijl+1;
       else {
        if(s==val) return mijl;
        dr=mijl-1;
       }
   }
   return -1;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++) { f>>x; add(i,x); }
    while(m!=0){
        m--;
        f>>c;
        if(c==0) { f>>a>>b; add(a,b); }
          else
        if(c==1) { f>>a>>b; g<<sum(b)-sum(a-1)<<'\n'; }
          else   { f>>a; g<<cautbin(a)<<'\n'; }
    }
    return 0;
}