#include<iostream>
#include<fstream>
#define NMAX 100001
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n,m;
int arb[NMAX];
void update(int poz,int val)
{
    int k=0;
    while(poz<=n)
    {
        arb[poz]+=val;
        while((poz&(1<<k))==0)
            k++;
        poz+=1<<k;
        k++;
    }
}
int query(int x)
{
    int k=0,s=0;
    while(x>0)
    {
        s+=arb[x];
        while((x&(1<<k))==0)k++;
        x-=1<<k;
    }

    return s;
}
int solve(int x)
{
    for(int i=1;i<=n;i++)
        if(query(i)==x)return i;
    return -1;
}
int main()
{   int x,a,b,op;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>x;
        update(i,x);
    }
  for(int i=1;i<=m;i++)
  {
      fin>>op;
      if(op==1)
      {
          fin>>a>>b;
          fout<<query(b)-query(a-1)<<'\n';
      }
      else
        if(op==0)
      {
          fin>>a>>b;
          update(a,b);
      }
      else
      {   fin>>a;
         int mij,st=1,dr=n,ret=-1;
         int s=query(dr);
         if(s==a)ret=n;
         else
         while(st<=dr)
         {
             mij=(st+dr)>>1;
             s=query(mij);
             if(s==a){ret=mij;break;}
             if(s<a)st=mij+1;
             if(s>a)dr=mij-1;
         }
         fout<<ret<<'\n';
      }
  }
fin.close();
fout.close();

return 0;
}