#define submit
#ifdef submit
    #define fisier "aib"
#else
    #define fisier "ULTRA"
#endif

#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");

const int
N = 100000,
M = 150000;

int n, m, v[N];

inline int primul_copil(int idx) {return ((idx+1) << 1) - 1;}
inline int al_doilea_copil(int idx) {return ((idx+1) << 1);}
inline int tata(int idx) {return ((idx+1) >> 1) - 1;}

void adauga_la_frunza(int idx_frunza, int val)
{
    for (; idx_frunza != -1; idx_frunza = tata(idx_frunza))
        v[idx_frunza] += val;
}

int frunza(int idx)
{
    int i = 0, j = n - 1, mij, idx_frunza = 0;
    //out << "\n\nsrch " << idx << std::endl;
    while (i < j)
    {
        //out << "i = " << i << ", j = " << j << std::endl;
        //out << "idx_frunza = " << idx_frunza << std::endl;
        mij = (i + j) >> 1;
        if (idx <= mij)
        {
            j = mij;
            idx_frunza = primul_copil(idx_frunza);
        }
        else
        {
            i = mij + 1;
            idx_frunza = al_doilea_copil(idx_frunza);
        }
    }

    //out << "i = " << i << ", j = " << j << std::endl;
    //out << "idx_frunza = " << idx_frunza << std::endl;
    return idx_frunza;
}

int interog_nod(int idx_nod, int off_i, int lun, int off_j)
{
    /*out << "interog_nod(" << idx_nod << ", " << off_i << ", " << lun << ", " << off_j << ")\n";
    for (int i = 0; i < off_i; i++)
        out << ". ";
    for (int i = 0; i < lun; i++)
        out << "x ";
    for (int i = 0; i < off_j; i++)
        out << ". ";
    out << "\n";*/

    bool lun_imp = (off_i ^ lun ^ off_j) & 1;
    int mij = (off_i + lun + off_j) >> 1;

    if (!off_i && !off_j) { //out << "caz de baza\n";
        return v[idx_nod]; }
    if (lun + off_j <= off_i - lun_imp) { //out << "pe dreapta -->\n";
        return interog_nod(al_doilea_copil(idx_nod), mij - off_j - lun - lun_imp, lun, off_j); }
    if (off_i + lun <= off_j + lun_imp) { //out << "<-- pe stanga\n";
        return interog_nod(primul_copil(idx_nod), off_i, lun, mij - off_i - lun + lun_imp); }
    //out << "<-- taietura -->\n";
    return
    interog_nod(primul_copil(idx_nod), off_i, lun_imp + mij - off_i, 0) +
    interog_nod(al_doilea_copil(idx_nod), 0, lun - lun_imp - mij + off_i, off_j);
}

inline void adauga(int idx, int val) {adauga_la_frunza(frunza(idx), val);}
inline int interogare_suma(int i, int j) {return interog_nod(0, i, j - i + 1, n - j - 1);}
int poz_min(int val)
{
    int i = 0, j = n - 1, mij;

    while (i <= j)
        if (interogare_suma(0, mij = (i + j) >> 1) < val)
            i = mij+1;
        else
            j = mij-1;

    if (interogare_suma(0, i) == val)
        return i;
    else
        return -2;
}


int main()
{
    in >> n >> m;

    for (int i = 0; i < n; i++)
    {
        int itr; in >> itr;
        adauga(i, itr);
    }

    while (m--)
    {
        int op, a, b;
        in >> op >> a;
        if (op < 2)
            in >> b;

        /*out << "v = ";
        for (int i = 0; i < n; i++)
            out << interogare_suma(i, i) << ' ';
        out << std::endl;*/

        switch (op)
        {
            case 0:
                adauga(a-1, b);
                break;
            case 1:
                out << interogare_suma(a-1, b-1) << '\n';
                break;
            case 2:
                out << poz_min(a)+1 << '\n';
                break;
        }
    }
}