#include <cstdio>
#define nr_zerouri(x) ((x ^ (x  - 1)) & x)
using namespace std;
const int NMAX = 100005;
int aib[NMAX * 4];
int v[NMAX];
void update(int val, int poz, int n) {
  while(poz <= n) {
    aib[poz] += val;
    poz += nr_zerouri(poz);
  }
}
int suma(int poz, int n) {
  int sol = 0;
  while(poz) {
    sol += aib[poz];
    poz -= nr_zerouri(poz);
  }
  return sol;
}
int cautare_binara(int a, int n) {
  int sol = -1;
  int st = 1, dr = n;
  while(st <= dr) {
    int mij = (st + dr) / 2;
    int s = suma(mij, n);
    if(s < a) {
      st = mij + 1;
    }
    else {
      if(a == s) {
        sol = mij;
      }
      dr = mij - 1;
    }
  }
  return sol;
}

int main() {
  int n, m;
  freopen("aib.in", "r", stdin);
  freopen("aib.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; ++i) {
    scanf("%d", &v[i]);
    update(v[i], i, n);
  }
  for(int i = 1; i <= m; ++i) {
    int op, a;
    scanf("%d%d", &op, &a);
    if(op == 0) {
      int b;
      scanf("%d", &b);
      update(b, a, n);
    }
    else if(op == 1) {
      int b;
      scanf("%d", &b);
      printf("%d\n", suma(b, n) - suma(a - 1, n));
    }
    else if(op == 2) {
      printf("%d\n", cautare_binara(a, n));
    }
  }
  return 0;
}