#include <fstream>
using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

const int MAXN = 100009;

int N, Q, pas;
int aib[MAXN];

inline int query(int poz)
{
    int sum = 0;
    while ( poz != 0 )
    {
        sum += aib[poz];
        poz -= poz&-poz;
    }

    return sum;
}

inline void update(int poz, int val)
{
    while ( poz <= N )
    {
        aib[poz] += val;
        poz+=poz&-poz;
    }
}

inline int cauta(int val)
{
    int step = pas, i = 0, sum = val--;

    for ( ; step; step>>=1)
        if ( i+step <= N && aib[i+step] <= val )
        {
            i+= step;
            val -= aib[i];
        }

    if ( query(i+1) == sum )
        return i+1;
    else
        return -1;
}

void citire()
{
    int tip, poz, val, st, dr;

    fin >> N >> Q;
    for (int i = 1; i <= N; ++i)
    {
        fin >> val;
        update(i, val);
    }

    for ( pas = 1; pas <= N; pas<<=1);

    for (int i = 0; i < Q; ++i)
    {
        fin >> tip;
        if ( tip == 0 )
        {
            fin >> poz >> val;
            update(poz, val);
        }
        else if ( tip == 1 )
        {
            fin >> st >> dr;
            fout << query(dr) - query(st-1) << "\n";
        }
        else
        {
            fin >> val;
            fout << cauta(val) << "\n";
        }
    }
}

int main ()
{
    citire();

    fin.close();
    fout.close();

    return 0;
}