#include<stdio.h>
#define NMAX 100001

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

int nz(long k) {
  int z=0;
  while(k%2==0) { z++; k>>=1; }
  return z;
}

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

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

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

long poz(long k) {
  long s,mid,a=1,b=n;
  s=sum(a);
  while(a!=b) {
    mid=a+(b-a)/2;
    s=sum(mid);
    if(k<s) b=mid; else if(k>s) a=mid+1; else a=b=mid;
  }
  return (s==k)?a:-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;
}