#include <fstream>

#define MAXN 100005

using namespace std;

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

int N, M, aib[MAXN * 3];

inline void Update(int poz, int val) {
    for (int i = poz; i <= N; i += i & (-i))
        aib[i] += val;
}

inline int Query(int a, int b) {
    int sol = 0;

    for (int i = b; i; i -= i & (-i))
        sol += aib[i];
    for (int i = a - 1; i; i -= i & (-i))
        sol -= aib[i];
    return sol;
}

inline int BinarySearch(int a) {
    int step, ii, poz = MAXN, aux;
    for (step = 1; step <= N; step <<= 1);
    for (ii = 0; step; step >>= 1) {
        if (ii + step <= N) {
            aux = Query(1, ii + step);
            if (aux < a)
                ii += step;
            else if (aux == a) {
                if (poz > ii + step)
                    poz = ii + step;
            }
        }
    }
    if (poz != MAXN)
        return poz;
    return -1;
}

inline void Read() {
    int x, tip, y;

    fin >> N >> M;

    for (int i = 1; i <= N; i++) {
        fin >> x;

        Update(i, x);
    }

    while (M--) {
        fin >> tip >> x;

        if (tip == 0) {
            fin >> y;
            Update(x, y);
        }
        else if (tip == 1) {
            fin >> y;
            fout << Query(x, y) << "\n";
        }
        else {
            fout << BinarySearch(x) << "\n";
        }
    }
}

int main () {
    Read();

    fin.close(); fout.close(); return 0;
}