#include <fstream>
using namespace std;

int n, m;

struct tripla {
    int op, a, b;
};

tripla Q[150001];
int a[100001];
int fw[100001];

void read() {
    int i;
    ifstream f("aib.in");
    f >> n >> m;
    for (i = 1; i <= n; i++)
        f >> a[i];
    for (i = 1; i <= m; i++) {
        f >> Q[i].op;
        if (Q[i].op == 0 || Q[i].op == 1)
            f >> Q[i].a >> Q[i].b;
        else f >> Q[i].a;
    }
    f.close();
}

void update(int ind, int val) {
    while (ind <= n) {
        fw[ind] += val;
        ind += (ind & -ind);
    }
}

long long getSum(int ind) {
    long long s = 0;
    while (ind) {
        s += fw[ind];
        ind -= (ind & -ind);
    }
    return s;
}

void solve() {
    int i;
    for (i = 1; i <= n; i++)
        update(i, a[i]);
}

int bs(int x) {
    int st, dr, mij, poz = -1;
    st = 1, dr = n;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if (getSum(mij) >= x) {
            dr = mij - 1;
            poz = mij;
        }
        else st = mij + 1;
    }
    return poz;
}

void output() {
    int i;
    ofstream g("aib.out");
    for (i = 1; i <= m; i++)
        if (Q[i].op == 0) 
            update(Q[i].a, Q[i].b);
        else if (Q[i].op == 1) 
            g << getSum(Q[i].b) - getSum(Q[i].a - 1) << '\n';
        else 
            g << bs(Q[i].a) << '\n';
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}