#include<stdio.h>
#include<string.h>
#define zero(x)((x^(x-1))&x)
FILE*fin=fopen("aib.in","r");
FILE*fout=fopen("aib.out","w");
int n,s[100001],m,tree[100001];
void add(int a,int b)
{
  while(a<=n)
  {
    tree[a]+=b;
    a+=zero(a);
  }
}
int sum(int a)
{
  int rez=0;
  while(a>0)
  {
    rez+=tree[a];
    a-=zero(a);
  }
  return rez;
}
int main()
{
  int i,o,a,b,st,dr,mij;
  fscanf(fin,"%d%d",&n,&m);
  for(i=1;i<=n;i++)
    fscanf(fin,"%d",&s[i]);
  memset(tree,0,sizeof(tree));
  for(i=1;i<=n;i++)
    add(i,s[i]);
  for(i=1;i<=m;i++)
  {
    fscanf(fin,"%d",&o);
    if(o==0)
    {
      fscanf(fin,"%d%d",&a,&b);
      add(a,b);
    }
    if(o==1)
    {
      fscanf(fin,"%d%d",&a,&b);
      fprintf(fout,"%d\n",sum(b)-sum(a-1));
    }
    if(o==2)
    {
      fscanf(fin,"%d",&a);
      st=1;dr=n;
      while(st<dr)
      {
	mij=(st+dr)/2;
	if(sum(mij)>=a) dr=mij;
	else st=mij+1;
      }
      if(sum(st)==a) fprintf(fout,"%d\n",st);
      else fprintf(fout,"-1\n");
    }
  }
  fclose(fin);
  fclose(fout);
  return 0;
}