#include<stdio.h>
#define NMAX 100001

long c[NMAX],n,m,k,i,op,a,b;

void add(long i,long k) {
  while(i<=n) {
    c[i]+=k;
    i+=i^(i&(i-1));
  }
}

long sum(int i) {
  long s=0;
  while(i) {
    s+=c[i];
    i-=i^(i&(i-1));
  }
  return s;
}

long sum(long a,long b) { return sum(b)-sum(a-1); }

long poz(long k) {
  int i=0,st=1;
  while(st<k) st<<=1;
  while(st) {
    if((i+st<=n)&&(k>=c[i+st])) {
      i+=st;
      k-=c[i];
      if(!k) return i;
    }
    st>>=1;
  }
  return -1;
}

int main() {
  freopen("aib.in","r",stdin);
  freopen("aib.out","w",stdout);
  scanf("%ld %ld",&n,&m);
  for(i=1;i<=n;i++) c[i]=0;
  for(i=1;i<=n;i++) { scanf("%ld",&k); add(i,k); }
  for(i=0;i<m;i++) {
    scanf("%ld %ld",&op,&a);
    if(op!=2) scanf("%ld",&b);
    switch(op) {
      case 0: add(a,b); break;
      case 1: printf("%ld\n",sum(a,b)); break;
      case 2: printf("%ld\n",poz(a)); break;
    }
  }
  fclose(stdin);
  fclose(stdout);
  return 0;
}