#include <iostream>
#include <fstream>
#define nmax 100007
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
long a[nmax],n;

long cauta(long);
int main()
{long k,x,y,poz,p,op,suma,sumb,i;
    fin>>n>>k;
    for(i=1;i<=n;i++)
    {fin>>x;
    poz=i;p=0;
     while(poz<=n)
      {a[poz]+=x;
          while(!((poz>>p) & 1))p++;
         poz+=(1<<p);
      }
    }


for(i=1;i<=k;i++)
{fin>>op;
if(op==0)
    {fin>>x>>y;
        poz=x;p=0;
    while(poz<=n)
        {a[poz]+=y;
        while(!((poz>>p) & 1))p++;
        poz+=(1<<p);
        p++;
        }

    }
    else if(op==1)
    {fin>>x>>y;
        suma=sumb=0;
        poz=y;p=0;
        while(poz>0)
        {sumb+=a[poz];
        while(!((poz>>p) & 1))p++;
        poz-=(1<<p);p++;
        }

        poz=x-1;p=0;
        while(poz>0)
        {suma+=a[poz];
        while(!((poz>>p) & 1))p++;
        poz-=(1<<p);p++;
        }
        fout<<sumb-suma<<'\n';
    }
    else {fin>>x;
          fout<<cauta(x)<<'\n';
          }
    }

}


long cauta(long x)
{long j,p;
    for(p=1;p < n;p<<=1);

    for(j=0;p;p>>=1)
          if(j+p<=n)
            if(x>=a[j+p]){
                    j=j+p;x-=a[j];
                    if(!x) return j;
          }
    return -1;
}