#include <iostream>
#include <fstream>

using namespace std;

#define nmax 100001

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

int n, m;
int a, b, x, type;
int ARB[4*nmax];

void updateAib(int val, int pos)
{
    while (pos <= n)
    {
        ARB[pos] += val;
        pos += (pos^(pos-1))&pos;
    }
}

int queryAib(int pos)
{
    int S = 0;

    while (pos > 0)
    {
        S += ARB[pos];
        pos -= (pos^(pos-1))&pos;
    }

    return S;
}

int cautBin(int val)
{

    int rez = -1;

    int lo = 1, hi = n;

    while (lo <= hi)
    {

        int mid = (lo + hi) >> 1;

        int x = queryAib(mid);

        if (val == x)
        {
            rez = mid;
            break;
        }

        if (val < x)
            hi = mid - 1;
        else
            lo = mid + 1;

    }

    return rez;

}

int main()
{

    fi >> n >> m;

    for (int i = 1; i <= n; i++)
        fi >> x,
        updateAib(x, i); // val, pos

    for (int i = 1; i <= m; i++)
    {
        fi >> type;

        if (type == 0)
        {
            fi >> a >> b;
            updateAib(b, a); // val, pos
        }
        else if (type == 1)
        {
            fi >> a >> b;
            fo << queryAib(b) - queryAib(a-1) << "\n";
        }
        else
        {
            fi >> a;
            fo << cautBin(a) << "\n";
        }
    }

    fi.close();
    fo.close();

    return 0;
}