#include <iostream>
#include <fstream>

using namespace std;

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

const int MAXN = 100010;

int N, logN;
int AIB[MAXN];

inline int LSB (const int &X)
{
    return X & (-X);
}

inline void Update (const int &val, int poz)
{
    int i;

    for (i = poz; i <= N; i += LSB (i))
        AIB[i] += val;
}

inline int Query (const int &poz)
{
    int i;
    int ret = 0;

    for (i = poz; i; i -= LSB (i))
        ret += AIB[i];

    return ret;
}

inline int BS (int val)
{
    int i = 0, step;

    for (step = logN; step; step >>= 1){
        if (i + step <= N && AIB[i + step] <= val){
            i += step;
            val -= AIB[i];

            if (!val)
                return i;
        }
    }

    return -1;
}

int main()
{
    int M, a, b, op, i;

    in >> N >> M;
    for (i = 1; i <= N; i ++){
        in >> a;
        Update (a, i);
    }

    for (logN = 1; logN < N; logN <<= 1);

    for (i = 1; i <= M; i ++){
        in >> op;

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

        if (op == 1){
            in >> a >> b;
            out << Query (b) - Query (a - 1) << "\n";
        }

        if (op == 2){
            in >> a;
            out << BS (a) << "\n";
        }
    }

    return 0;
}