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

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

inline int zerosPow(int i) {
  return i ^ (i & (i-1));
}

void update(int i, int val) {  
  for (int x=i;x<=N;x+=zerosPow(x)) {
    aib[x] += val;    
  }
}

int query_sum(int b) {  
  int sum = 0;
  for (int x=b;x>0;x-=zerosPow(x)) {
    sum += aib[x];
  }
  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;
}