#include <bits/stdc++.h>
#include <unordered_map>
#include <map>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");
//-----------------------------------------
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>
//-----------------------------------------
#define f(i,s,e) for(int i=s;i<=e;++i)
#define nf(i,s,e) for(i=s;i<e;++i)
#define rf(i,e,s) for(i=e;i>=s;--i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define sp <<" "
//------------------------------------------
const int NMAX = 1e5 + 5;
const int KMAX = 1e1 + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
//------------------------------------------
int n,m;
int aib[NMAX];
int op;
//------------------------------------------
void update(int i,int x){
  while(i<=n){
    aib[i]+=x;
    i=i+(i&(-i));
  }
}
void read() {
  int x,y;
  fin>>n>>m;
  for(int i=1;i<=n;++i){
     fin>>x;
     update(i,x);
  }
}
int query(int x){
  int s=0;
  while(x>0){
    s+=aib[x];
    x=x-(x&(-x));
  }
  return s;
}
int Search(int x){
  int st=1,dr=n,mij,sol=-1;
  while(st<=dr){
    mij=(st+dr)/2;
    int rez=query(mij);
    if(rez==x){
      dr=mij-1;
      sol=mij;
    }
    else if(rez>x) dr=mij-1;
    else st=mij+1;
  }
  return sol;
}
void solve() {
  int x,y;
  for(int i=1;i<=m;++i){
    fin>>op;
    if(op==0){
      fin>>x>>y;
      update(x,y);
    }
    else if(op==1){
      fin>>x>>y;
      fout<<query(y)-query(x-1)<<"\n";
    }
    else{
      fin>>x;
      fout<<Search(x)<<"\n";
    }
  }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    read();
    solve();
    return 0;
}