#include <iostream>
#include <fstream>
using namespace std;
unsigned int n, m, a, b, op;
unsigned int bit[100002];
void update (unsigned int val, unsigned int pos)
{
    for(; pos<=n; pos += pos&-pos)
        bit[pos]+=val;
}
unsigned int sum (unsigned int x)
{
    unsigned int sum=0;
    for(; x>0; x-= x&-x)
        sum+=bit[x];
    return sum;
}
int search_k(unsigned int val)
{
    unsigned int iv, dif;
    for(iv=1;iv<=n;iv<<=1);  ///gasim puterea lu 2 cea mai mare, mai mica sau egala cu N

    for(dif=0; iv; iv>>=1)
    {
        if (dif+iv <=n)     ///dc avem o suma partiala din primele k<=n elem
        {
            if(val>=bit[dif+iv])    ///suma partiala e mai mica? cautam in dreapta; dc e mai mare for-ul injumatateste capatul intervalului
            {
                val-=bit[dif+iv];
                dif+=iv;
                if(!val)
                    return dif;
            }
        }
    }
    return -1;
}
int main ()
{
    ifstream input ("aib.in");
    ofstream output ("aib.out");
    input>>n>>m;
    for (int i = 1;i<=n;++i)
    {
        //cout<<i<<" ";
        input>>a;
        update(a, i);
    }
    for(int i = 0;i<m;++i)
    {
        input>>op;
        cout<<op<<" ";
        if(op==0)
        {
            input>>a>>b;
            update(b, a);
        }
        else if(op==1)
        {
            input>>a>>b;
            output<<sum(b)- sum(a-1)<<"\n";
        }
        else
        {
            input>>a;
            output<<search_k(a)<<"\n";
        }
    }
    input.close();
    output.close();
    return 0;

}