#include <fstream>
using namespace std;
#define NMAX 100001

int N, M, aib[NMAX];
ifstream f("aib.in"); ofstream g("aib.out");

void update(int i, int val) {
  int x, y, z;
  x = i;
  while (x<=N) {
    aib[x] += val;
    y = x, z = 0;
    while (!(y&1)) {
      z++;
      y>>=1;
    }
    x += (1<<z);
  }
}

int query_sum(int b) {  
  int sum = 0, y, z;
  while (b) {
    sum += aib[b];
    y=b, z=0;
    while (!(y&1)) {
      z++;
      y>>=1;
    }
    b -= (1<<z);
  }
  return sum;
}

int searchK(int sum) {
  int i, step;
  for (step=1;step<N;step<<=1);
  for (i=0;step;step>>=1) {
    if (i+step<=N && aib[i+step]<=sum) {
      i+=step;
      sum -= aib[i];
      if (!sum) return i;
    }
  }
  return -1;
}

int main() {
  int i, tip, a, b;
  f>>N>>M;
  for (i=1;i<=N;i++) {
    f >> a;
    update(i,a);
  }
  for (i=1;i<=M;i++) {
    f>>tip>>a;
    switch(tip) {
    case 0:
      f>>b;
      update(a,b);
      break;
    case 1:
      f>>b;
      g << query_sum(b)-query_sum(a-1) << "\n";
      break;
    case 2:
      g << searchK(a)<<"\n";
      break;
    }
  }

  f.close(); g.close(); return 0;
}