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

using namespace std;

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

const int Nmax = 100005;
const int Log = 20;

vector <int> MaxArb(Nmax);
int putere[Log];

int logaritm (int x)
{
    int nr = 0;

    while (x != 1)
        x = x / 2, nr++;

    return nr;
}

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 Find (int poz, int val)
{
    for (int i = poz; i >= 0; i--)
        if (MaxArb[putere[i]] == val)
            return putere[poz - i - 1];

    return -1;
}

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

    int nivel = logaritm(n) + 1;

    putere[0] = 1;
    for (int i = 1; i <= nivel; i++)
        putere[i] = putere[i - 1] * 2;

    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;
            int rez = -1;

            out << Find(nivel, a) << '\n';
        }
    }

    return 0;
}