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

int n;

struct BIT {
    vector<int> 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;
        }
    }
};

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 {
            int ans = -1, l = 1, r = n;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (aib.query(mid) == x) {
                    ans = mid;
                    break;
                }
                if (aib.query(mid) < x) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            cout << ans << '\n';
        }
    }


    return 0;
}