#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
#define nmax 100100
#define zeros(x) (x^(x-1)&x)
int aib[nmax],val,n;
void ad(int i)
{
    for(;i<=n;i+=zeros(i))
        aib[i]+=val;
}
int nr;
int cate(int i)
{
    nr=0;
    for(;i;i-=zeros(i))
        nr+=aib[i];
    return nr;
}
int poz,w;
int caut(int sum)
{
    for(poz=1;poz<=n;poz<<=1);
    w=poz;
    for(;poz;poz>>=1)
    {
        if(w-poz>=1 and cate(w-poz)>=sum)
        {
            w-=poz;
            }
    }
    if(cate(w)==sum)
        return w;
    else return -1;
}
int main()
{
    int i,x,y,k,m,tip;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>val;
        ad(i);
    }
    for(i=1;i<=m;i++)

    {
        f>>tip;
        if(tip==2)
        {
            f>>k;
            g<<caut(k)<<'\n';
        }
        else
        {
            f>>x>>y;
            if(tip==0)
            {
                val=y;
                ad(x);
            }
            else
            {
                g<<cate(y)-cate(x-1)<<'\n';
            }
        }
    }
    return 0;
}