#include <fstream>
#include <cstdio>
#define p2(x) ((x^(x-1))&x)
using namespace std;
ifstream fi ("aib.in");
ofstream fo ("aib.out");
int aib[100006],v[100006];
int nrel,nrop,op;
void adaug(int pozi,int el)
{
  while (pozi<=nrel) // winmerge
  {
    aib[pozi]+=el;
    pozi+=p2(pozi);
  }
}
int suma(int x)
{
  if (x==0) return 0;
  return aib[x]+suma(x-p2(x));
}
int pozmin(int suma)
{
  int i,bit=(1<<22);
  for (i=0;bit;bit>>=1)
    if (i+bit<=nrel)
    if (aib[i+bit]<=suma)
      {
        i+=bit,suma-=aib[i];
        if (suma==0)
          return i;
      }
  return-1;
}
int main()
{
  freopen("AIB.in","r",stdin);
  freopen("AIB.out","w",stdout);
  scanf("%d",&nrel);scanf("%d",&nrop);
  for (int i=1;i<=nrel;i++) scanf("%d", &v[i]);
  for (int i=1;i<=nrel;i++) adaug(i,v[i]);
//  for (int i=1;i<=nrel;i++) fo<<aib[i]<<' ';fo<<'\n';
  for (int i=1;i<=nrop;i++)
  {
    scanf("%d",&op);
    if (op==0)
    {
      int p,val;
      scanf("%d",&p);scanf("%d",&val);
      adaug(p,val);
    }
    if (op==1)
    {
      int p1,p2;
      scanf("%d",&p1);scanf("%d",&p2);
      fo<<suma(p2)-suma(p1-1)<<'\n';
    }
    if (op==2)
    {
      int sum;
      scanf("%d",&sum);
      fo<<pozmin(sum)<<'\n';
    }
  }
  return 0;
}