#include<fstream>
#define nmax 100002
using namespace std;
ifstream fin("aim.in");
ofstream fout("aim.out");
int n, m, v[nmax], c[nmax];
void display()
{

    for(int i = 1; i <= n; i++)
        fout <<c[i] <<" ";
    fout <<'\n';

}
void build()
{
    int val = 0, Nr = 0;
    bool ok;
    for(int i = 1; i <= n; ++i)
    {
        v[i] = v[i - 1] + v[i];//suma partiala
       // fout << v[i] <<" ";
    }
    for(int i = 1; i <= n; ++i)
    {
        val = 1  ; Nr = 0;
        while((i & val ) == false )// vedem cate zerouri are indicele curent
        {
            Nr++;
            val *= 2;
        }
        c[i] = v[i] - v[i - val ];//c[i] = sum(i - 2^Nr, i);

    }
}
void add(int poz, int val)
{
    int i, Nr, val2;
    Nr = 0;
    val2 = 1;
    while(poz <= n )
    {
        c[poz] += val;

        while( (poz & val2)==0)
        {
            val2*=2;
            Nr++;
        }
        poz+= val2;//nr de zerouri nu trebuie resetat, tot timpul va fi mai mare
    }

}
int sum(int st, int dr)
{
    int i, val = 1, poz, S = 0;
    st--;
    while(dr)
    {
        S+= c[dr];
        while((dr & val )==0)
            val*=2;
        dr -= val;
    }
    val = 1;
    while(st)
    {
        S-= c[st];
        while((st & val) == 0)
            val *= 2;
        st -= val;

    }
    return S;
}
int begin (int S)
{
    int K;
    int poz;
    for(poz = 1; c[poz] <= S  && poz <=n; poz *=2);
    poz/=2;
    K=poz;
    S -= c[poz];
    while(S > 0 && poz && K<=n )
    {
        poz /=2;
        if(c[K+poz] <=S)
        {
            K += poz;
            S -= c[K];
        }

    }
   // fout <<S<<'\n';
    if(!S)
        return K;
    else
        return -1;
}
void read()
{
    int poz, val, st, dr, S;
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        fin >>v[i];
    build();//construim structura arborescenta cu valorile initiale
    for(int i = 1; i <= m; i++)
    {
        int s;
        fin>>s;
        if(s == 0)
        {
            fin >>poz >>val;
            add(poz, val); //adaugam elemntului poz, val
        }
        if(s == 1)
        {
            fin >> st >>dr;
            fout <<  sum(st, dr) <<'\n';
        }
        if(s == 2)
        {
            fin >> S;
            fout << begin(S) <<'\n';
        }
    }


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