#include<fstream>
#define nmax 100005
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
long n, m ;
long c[nmax];
//in c[x] retinem suma de la [x - 2^nr, x], unde nr = nr de zerouri al lui x
void add(long poz, long val)
{
    long i, Nr, val2;
    Nr = 0;

    while(poz <= n )
    {
        c[poz] += val;

        while( (poz & (1<<Nr) )==0 ) Nr++;

        poz+= (1<<Nr); Nr++;//nr de zerouri nu trebuie resetat, tot timpul va fi mai mare
    }

}

long sum(long x)
{
    long  S = 0, nr =0 ;
   while(x)
   {
       S += c[x];
       while( x & (1 <<nr) == 0) nr++;

       x -= (1<<nr);
       nr++;
   }
    return S;
}
long begin (long S)
{

    long step, i;
    for(step = 1; step <= n; step <<=1);

    for(i = 0; step ; step >>= 1)
       {
           if(i + step <= n && S >= c[i+ step])
           {
               i += step;
               S -= c[i];
               if(!S)
                return i;
           }
       }
    return -1;
}
void read()
{
    long poz, val, st, dr, S, x;
    fin >> n >> m;
    for(long i = 1; i <= n; i++)
    {
        fin >>x;
        add(i, x);
    }

   // build();//construim structura arborescenta cu valorile initiale
    for(long i = 1; i <= m; i++)
    {
        long s;
        fin>>s;
        if(s == 0)
        {
            fin >>poz >>val;
            add(poz, val); //adaugam elemntului poz, val
        }
        if(s == 1)
        {
            fin >> st >>dr;
            fout <<  sum(dr) - sum(st - 1) <<'\n';
        }
        if(s == 2)
        {
            fin >> S;
            fout << begin(S) <<'\n';
        }
    }


}
int  main()
{
    read();
//    bool ok;
//    ok = 16 & 16;
//    fout <<ok;
    fin.close();
    return 0;
}