#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;

int aib[NMAX+1], N;

void update(int poz, int v) {
    while(poz <= N) {
        aib[poz] += v;
        poz += poz & (-poz);
    }
}

int sum(int poz) {
    int s = 0;
    while(poz > 0) {
        s += aib[poz];
        poz -= poz & (-poz);
    }
    return s;
}

int bs(int v) {
    int p = 1, u = N, poz = -1;
    while(p <= u) {
        int m = (p+u)/2,
            s = sum(m);

            if(s < v) p = m+1;
            else {
                if(s == v) poz = m;
                u = m-1;
            }
    }
    return poz;
}

int main()
{
    int M, op, x, y;
    in >> N >> M;
    for(int i = 1; i <= N; i++) {
        in >> x;
        update(i, x);
    }

    while(M--) {
        in >> op;
        switch(op) {
            case 0:
                in >> x >> y;
                update(x, y);
                break;
            case 1:
                in >> x >> y;
                out << sum(y) - sum(x-1) << '\n';
                break;
            case 2:
                in >> x;
                out << bs(x) << '\n';
        }
    }
    return 0;
}