#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
#define nmax 100100
#define zero(x) (x^(x-1)&x)
int aib[nmax],i,vale,x,n;
void ad(int i)
{
    for(;i<=n;i+=zero(i))
        aib[i]+=vale;
}
int val(int i)
{
    int s=0;
    for(;i;i-=zero(i))
        s+=aib[i];
    return s;
}
int maxim;
int caut(int x)
{
    int poz=0;
    i=maxim;
    for(;i;i/=2)
    {
        if(i+poz<=n and val(i+poz)<=x)
            poz+=i;
    }
    if(val(poz)==x)
        return poz;
    else
        return -1;
}
int main()
{
    int q,tip,y,w,i;
    f>>n>>q;
    for(maxim=1;maxim<=n;maxim*=2);
    for(i=1;i<=n;i++)
    {
        f>>x;
        vale=x;
        ad(i);
    }
    for(i=1;i<=q;i++)
    {
        f>>tip;
        if(tip==0)
        {
            f>>w>>x;
            vale=x;
            ad(w);
        }
        else
            if(tip==1)
            {
                f>>x>>y;
                g<<val(y)-val(x-1)<<'\n';
            }
            else
            {
                f>>x;
                g<<caut(x)<<'\n';
            }


    }
    return 0;
}