#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+2;
const int LMAX = 18;
int n,q;

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

struct AIB {
  int n;
  vector<int> bit;
  AIB(){}
  AIB(int _n){
    n = _n;
    bit.resize(n+1);
  }
  void update(int pos, int val){
    for(int i = pos; i <= n; i += (i&-i)){
      bit[i] += val;
    }
  }
  int query(int pos){
    int ans = 0;
    for(int i = pos; i > 0; i -= (i&-i)){
      ans += bit[i];
    }
    return ans;
  }
  int range(int l, int r){
    return query(r) - query(l-1);
  }
  int kth(int k){
    int sum = 0, pos = 0;
    for(int i = LMAX; i >= 0; i--){
      int nwpos = pos+(1<<i);
      if(nwpos > n){
        continue;
      }
      int delta = bit[nwpos];
      if(sum+delta <= k){
        sum += delta;
        pos = nwpos;
      }
    }
    return (sum == k) ? pos : -1;
  }
};

int main() {
  fin >> n >> q;
  AIB aib(n);
  for(int i = 1; i <= n; i++){
    int x;
    fin >> x;
    aib.update(i, x);
  }
  while(q--){
    int t, a, b;
    fin >> t >> a;
    if(t == 0){
      fin >> b;
      aib.update(a, b);
    }else if(t == 1){
      fin >> b;
      fout << aib.range(a, b) << "\n";
    }else{ // t == 2
      fout << aib.kth(a) << "\n";
    }
  }
  return 0;
}