#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int Nmax = 100005;

vector <int> MaxArb(Nmax * 3);

void Update (int poz, int val, int nod, int st, int dr)
{
    if (st == dr)
    {
        MaxArb[nod] = MaxArb[nod] + val;
        return;
    }

    int mij = (st + dr) / 2;

    if (poz <= mij)
        Update (poz, val, nod * 2, st, mij);
    else
        Update (poz, val, nod * 2 + 1, mij + 1, dr);

    MaxArb[nod] = MaxArb[nod * 2] + MaxArb[nod * 2 + 1];
}

void Query (int &suma, int Start, int Final, int nod, int st, int dr)
{
    if (st >= Start && dr <= Final)
    {
        suma = suma + MaxArb[nod];
        return;
    }

    int mij = (st + dr) / 2;

    if (Start <= mij) Query (suma, Start, Final, nod * 2, st, mij);
    if (Final > mij)  Query (suma, Start, Final, nod * 2 + 1, mij + 1, dr);
}

int b_search(int n, int val)
{
    int cnt = 1;
    int rez = n;

    while (MaxArb[cnt] != val && cnt < Nmax * 3 - 1)
    {
        cnt = cnt * 2;
        rez = (rez + 1) / 2;
    }

    if (rez == 0)
        return -1;
    return rez;
}

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

    for (int i = 1; i <= n; i++)
    {
        int x;
        in >> x;

        Update (i, x, 1, 1, n);
    }

    for (int i = 1; i <= m; i++)
    {
        int op, a, b;
        in >> op;

        if (op == 0)
        {
            in >> a >> b;
            Update (a, b, 1, 1, n);
        }

        else

        if (op == 1)
        {
            in >> a >> b;

            int suma = 0;
            Query (suma, a, b, 1, 1, n);
            out << suma << '\n';
        }

        else

        {
            in >> a;
            out << b_search(n, a) << '\n';
        }
    }

    return 0;
}