#include <fstream>

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

int const nmax = 100005;
int aib[nmax];
int n;

void update (int x, int val) {
    for (int i = x; i <= n; i += ((i ^ (i - 1)) & i))
        aib[i] += val;
}

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

int bs (int value) {
    int st = 1, dr = n + 1;
    while (st < dr) {
        int med = (st + dr) >> 1;
        if (calc(med) < value)
            st = med + 1;
        else
            dr = med;
    }
    return dr;
}

int main() {
    int m;
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        update(i, x);
    }
    for (int i = m; i; i--) {
        int tip;
        fin >> tip;
        if (tip == 0) {
            int a, b;
            fin >> a >> b;
            update(a, b);
        } else if (tip == 1) {
            int a, b;
            fin >> a >> b;
            fout << calc(b) - calc(a - 1) << "\n";
        } else {
            int a;
            fin >> a;
            int aux = bs(a);
            if (a == n + 1)
                fout << "-1\n";
            else
                fout << bs(a) << "\n";
        }
    }
    return 0;
}