#include <iostream>
#include <fstream>

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int n, nr_intrebari, x, tip, a, b, valoare_ceruta;
int arbore[100005];

void update(int nr, int ind)
{
    while (ind<=n)
    {
        arbore[ind]+=nr;
        ind=ind+(ind&(-ind));
    }
}

int query(int ind)
{
    int s=0;
    while (ind)
    {
        s+=arbore[ind];
        ind=ind-(ind&(-ind));
    }
    return s;
}

void solve0()
{
    f >> a >> b;
    update(b,a);
}

void solve1()
{
    f >> a >> b;
    int v2=query(b);
    int v1=query(a-1);
    g << query(b)-query(a-1) << '\n';
}

void solve2()
{
    int putere=0, incepere=1;
    f >> valoare_ceruta;
    for (putere=1; putere<n; putere<<=1);
    for (incepere=0; putere!=0; putere>>=1)
    {
        if (incepere+putere<=n)
        {
            if (arbore[incepere+putere]<=valoare_ceruta)
            {
                valoare_ceruta-=arbore[incepere+putere];
                incepere+=putere;
                if (valoare_ceruta==0)
                {
                    g << incepere << '\n';
                    return;
                }
            }
        }
    }
    g << -1<< '\n';
}

int main()
{
    f >> n >> nr_intrebari;
    for (int i=1; i<=n; ++i)
    {
        f >> x;
        update(x,i);
    }
    for (int q=1; q<=nr_intrebari; ++q)
    {
        f >> tip;
        if (tip==0)
        {
            solve0();
        }
        else if (tip==1)
        {
            solve1();
        }
        else
            solve2();
    }
    return 0;
}