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

int n;

struct BIT {
    vector<long long> aib;

    BIT(int n) {
        aib.resize(n);
    }

    long long query(int i) {
        long long ans = 0;
        for (; i > 0; i -= i & (-i)) {
            ans += aib[i];
        }
        return ans;
    }

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

    long long binaryLift(long long k) {
        long long ans = 0;
        for (int pas = 1 << 19; pas > 0; pas >>= 1) {
            if (ans + pas <= n && aib[ans + pas] < k) {
                ans += pas;
                k -= aib[ans];
            }
        }
        return ans + 1;
    }
};

signed main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
#endif

    int m; cin >> n >> m;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }

    BIT aib(n + 1);
    for (int i = 1; i <= n; ++i) {
        aib.update(i, v[i]);
    }

    while (m--) {
        int op, x, y; cin >> op >> x;
        if (op < 2)
            cin >> y;
        if (op == 0)
            aib.update(x, y);
        else if (op == 1)
            cout << aib.query(y) - aib.query(x - 1) << '\n';
        else
            cout << aib.binaryLift(x) << '\n';
    }


    return 0;
}