#include <bits/stdc++.h>
#define NMAX 100000

using namespace std;

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

int n, q, op;
int aib[NMAX + 2], x, a, b, poz, val;

int urm_p2(int x) {
    return (x & (-x));
}

void add(int x, int y) {
    for (int i = x; i <= n; i += urm_p2(i)) {
        aib[i] += y;
    }
}

int sum(int x) {
    int rez = 0;
    for (int i = x; i >= 1; i -= urm_p2(i)) {
        rez += aib[i];
    }
    return rez;
}

int main() {
    fin >> n >> q;
    for (int i = 1; i <= n; i++) {
        fin >> x;
        add(i, x);
    }

    while (q--) {
        fin >> op;
        if (op == 0) {
            fin >> poz >> val;
            add(poz, val);
        }
        else if (op == 1) {
            fin >> a >> b;
            fout << sum(b) - sum(a - 1) << '\n';
        }
        else {
            fin >> a;
            poz = -1;
            int st = 1, dr = n;
            while (st <= dr) {
                int mij = (st + dr) >> 1;
                int s = sum(mij);
                if (s == a) {
                    poz = mij;
                    break;;
                }
                else if (s > a) {
                    dr = mij - 1;
                }
                else {
                    st = mij + 1;
                }
            }
            fout << poz << '\n';
        }
    }
    return 0;
}