#include<stdio.h>
#define NMAX 100001

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

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

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

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

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

int poz(int a,int b,int k) {
  int mid=a+(b-a)/2;
  int s=sum(mid);
  if(a==b) return (s==k)?a:-1;
  else return (k<s)?((a!=mid)?poz(a,mid-1,k):-1):((k>s)?poz(mid+1,b,k):mid);
}

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