#include <bits/stdc++.h>

#define N 100005 
#define oo 0x3f3f3f3f
#define zeros(x) ((x ^ (x - 1) & x))

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n, m;
int aib[N];

void update(int value, int position) {
  for(int i = position;i <= n;i += zeros(i)) {
    aib[i] += value;
  }
}

int query(int position) {
  int sum = 0;
  for(int i = position;i >= 1;i -= zeros(i)) {
    sum += aib[i];
  }
  return sum;
}

int find(int value) {
  int rep;
  for(rep = 1;rep <= n;rep <<= 1);
  for(int i = 0;rep;rep >>= 1) {
    if(i + rep <= n && aib[i + rep] <= value) {
      i += rep;
      value -= aib[i];
      if(!value) {
        return i;
      }
    }
  }
  return -1;
}

void read() {
  f>>n>>m;
  int x;
  for(int i = 1;i <= n;++i) {
    f>>x;
    update(x, i);
  }
}

void solve() {
  int x, a, b;
  for(int i = 1;i <= m;++i) {
    f>>x;
    if(!x) {
      f>>a>>b;
      update(b, a);
    }
    else if(x == 1) {
      f>>a>>b;
      g<<query(b) - query(a - 1)<<'\n';
    }
    else {
      f>>a;
      g<<find(a)<<'\n';
    }
  }
  f.close();
  g.close();
}


int main() {
  read();
  solve();
  return 0;
}