#include <bits/stdc++.h>
#define INFILE "aib.in"
#define OUTFILE "aib.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
const int NMAX=100001;
array<int,NMAX>BIT;
int n,m;
void UpdateBit(int x,int delta){
  for(;x<=n;x+=x&-x)
    BIT[x]+=delta;
}
int Query(int x){
  int sum=0;
  for(;x>0;x-=x&-x)
    sum+=BIT[x];
  return sum;
}
int Query(int a,int b){
  return Query(b)-Query(a-1);
}
int f(int k,int a){
  return Query(k)>=a;
}
int FindK(int a){
  int low=1;
  int high=n+1;
  while(low!=high){
    int mid=(low+high)/2;
    if(f(mid,a)==true){
      high=mid;
    }
    else{
      low=mid+1;
    }
  }
  int k=high;
  if(Query(k)==a)
    return k;
  return -1;
}

int main(){
  in>>n>>m;
  for(int i=1;i<=n;i++){
    int x;
    in>>x;
    UpdateBit(i,x);
  }
  for(int i=1;i<=m;i++){
    int tip;
    in>>tip;
    if(tip==0){
      int a,b;
      in>>a>>b;
      UpdateBit(a,b);
    }
    else if(tip==1){
      int a,b;
      in>>a>>b;
      out<<Query(a,b)<<"\n";
    }
    else if(tip==2){
      int a;
      in>>a;
      out<<FindK(a)<<"\n";
    }
  }
  return 0;
}