#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

class FenwickTree {
    public:
        FenwickTree(int n): n(n), data(n + 1, 0) {}
        void add(int where, int value) {
            for (; where <= n; where += lsb(where)) {
                data[where] += value;
            }
        }
        int query(int where) const {
            int answer = 0;
            for (; where; where -= lsb(where)) {
                answer += data[where];
            }
            return answer;
        }
        int size() const {
            return n;
        }
    private:
        int n;
        vector<int> data;

        int lsb(int x) const {
            return (x ^ (x - 1)) & x;
        }
};

int caut_bin(const FenwickTree &T, int key) {
    int lo = 0, hi = T.size();
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        int val = T.query(mid);
        if (val == key) {
            while (T.query(mid - 1) == key) {
                --mid;
            }
            return mid;
        } else if (val < key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return -1;
}

int main()
{
    int n, m;

    ifstream cin("aib.in");
    ofstream cout("aib.out");

    cin >> n >> m;
    FenwickTree T(n);
    int a, b;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        T.add(i, a);
    }

    while (m--) {
        int op;
        cin >> op;

        switch (op) {
        case 0:
            cin >> a >> b;
            T.add(a, b);
            break;
        case 1:
            cin >> a >> b;
            cout << (T.query(b) - T.query(a - 1)) << '\n';
            break;
        case 2:
            cin >> a;
            cout << caut_bin(T, a) << '\n';
            break;
        }
    }

    return 0;
}