#include <bits/stdc++.h>

using namespace std;

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

const int n_max = 100005;
int n, aib[n_max];

inline void Update(int p, int x) {
    while (p <= n) {
        aib[p] += x;
        p += (p & (-p));
    }
}

int Query(int p) {
    int s = 0;
    while (p) {
        s += aib[p];
        p -= (p & (-p));
    }
    return s;
}

int BS(int a) {
    int st, dr, mid, p, x;
    st = 1;
    dr = n;
    p = -1;
    while (st <= dr) {
        mid = (st + dr) / 2;
        x = Query(mid);
        if (x == a) {
            p = mid;
            dr = mid - 1;
        }
        else if (x > a) {
            dr = mid - 1;
        }
        else {
            st = mid + 1;
        }
    }
    return p;
}

int main() {
    int q, i, x, op, a, b;
    fin >> n >> q;
    for (i = 1; i <= n; i++) {
        fin >> x;
        Update(i, x);
    }
    while (q--) {
        fin >> op;
        switch (op) {
        case 0 :
            fin >> a >> b;
            Update(a, b);
            break;
        case 1 :
            fin >> a >> b;
            fout << Query(b) - Query(a - 1) << "\n";
            break;
        default :
            fin >> a;
            fout << BS(a) << "\n";
        }
    }
    return 0;
}