#include <bits/stdc++.h>
using namespace std;

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

#define cin fin
#define cout fout

int n, m, op, a, b;
vector<int> v;

struct aib {
    int n;
    vector<int> f;

    aib(int nn) {
        n = nn;
        f.assign(n + 1, 0);
    }

    void update(int i, int v) {
        for (; i <= n; i += (i & -i)) {
            f[i] += v;
        }
    }

    int query(int i) {
        int s = 0;

        for (; i > 0; i -= (i & -i)) {
            s += f[i];
        }

        return s;
    }
};

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> m;

    v.assign(n, 0);
    aib A(n);

    for (int i = 0; i < n; ++i) {
        cin >> v[i];

        A.update(i + 1, v[i]);
    }

    for (int i = 0; i < m; ++i) {
        cin >> op >> a;

        if (op == 0) {
            cin >> b;

            A.update(a, b);
        } else if (op == 1) {
            cin >> b;

            cout << A.query(b) - A.query(a - 1) << '\n';
        } else {
            int st = 1, dr = n, mij, rez = -1;

            while (st <= dr) {
                mij = (st + dr) / 2;

                if (A.query(mij) < a) {
                    st = mij + 1;
                } else if (A.query(mij) == a) {
                    dr = mij - 1;
                    rez = mij;
                } else {
                    dr = mij - 1;
                }
            }

            cout << rez << '\n';
        }
    }
}