#include <bits/stdc++.h>
#define DMAX 100100
#define zeros(x) ( (x ^ (x - 1)) & x )
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int a[DMAX],AIB[DMAX];
void citire();
int n,m,op;
void constr(int poz,int cat);
int cautbinar(int cat);
int Suma(int x);
int main()
{
   citire();

}
void citire()
{int i;
int x,y;
    fin>>n>>m;
    for(i=1;i<=n;i++)
        {fin>>x;constr(i,x);}
    for(i=1;i<=m;i++)
    {
        fin>>op;
        if(!op)
        {   fin>>x>>y;
            constr(x,y);

        }
        else
        if(op==1)
        {fin>>x>>y;
            fout<<Suma(y)-Suma(x-1)<<'\n';
        }
        else
        {
            fin>>x;
            fout<<cautbinar(x)<<'\n';
        }

    }


}
void constr(int poz,int cat)
{
    int i;
    for(i=poz;i<=n;i+= zeros(i))
        AIB[i]+=cat;
}
int Suma(int x)
{
    int i,ret=0;
    for(i=x;i>0;i-=zeros(i))
        ret+=AIB[i];
    return ret;
}
int cautbinar(int cat)
{
    int st=0,dr=n+1,mij;
    while(dr-st>1)
    {
        mij=(st+dr)/2;
        if(Suma(mij)<cat)
            st=mij;
        else
            dr=mij;
    }
    if(Suma(dr)==cat)
        return dr;
    return -1;
}