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

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) {
    int x;
    scanf("%d", &x);
    actualizare(x, i, n);
  }
  for(int q = 0; q < m; ++q) {
    int t, a, b;
    scanf("%d%d", &t, &a);
    if(t == 0) {
      scanf("%d", &b);
      actualizare(b, a, n);
    }
    else if(t == 1) {
      scanf("%d", &b);
      printf("%d\n", suma(b, n) - suma(a - 1, n));
    }
    else if(t == 2) {
      printf("%d\n", cautare_binara(a, n));
    }
  }
  return 0;
}