#include<fstream>
using namespace std;
int aib[100005];
int N;
const int p2[32]={ 1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072 };

void update(int p,int val){
     int c=0;
     while(p<=N){
        aib[p]+=val;
        while(!(p & p2[c]))c++;
        p+=p2[c];
        c++;
        }   
     }

int query(int p){
     int s=0,c=0;
     while(p>0){
          s+=aib[p];
          while(!(p & p2[c]))++c;    
          p-=p2[c];
          ++c;
              }
     return s;
     }

int bsearch(int k){
    int lb=1,ub=N,mid,sol=0;
    while(lb<=ub){
      mid=(ub+lb)>>1;
      if(query(mid)>=k){
                        sol=mid;
                        ub=mid-1;
                        }                                               
        else lb=mid+1;
        }                          
    if(query(sol)==k)return sol;
    return -1;                                                  
}

int main(void){
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    int m,i,q,w,cod;
    fin>>N>>m;
    for(i=1;i<=N;++i){ fin>>q; update(i,q); }

    for(i=1;i<=m;++i)
      {
       fin>>cod;
       if(cod!=2)
         {
          fin>>q>>w;
          if(cod==0)update(q,w);
            else fout<<query(w)-query(q-1)<<'\n';                  
          }     
         else {
              fin>>q;
              fout<<bsearch(q)<<'\n'; 
              }        
      }
 return 0;   
}