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

using namespace std;

const int LOGN = 17;
const int LOGSTEP = 1 << LOGN;

class FenwickTree {
    public:
        FenwickTree(int n): n(n), data(n + 1, 0) {}
        void add(int idx, int value) {
            while (idx <= n) {
                data[idx] += value;
                idx += lsb(idx);
            }
        }
        int query(int idx) const {
            int answer = 0;
            while (idx > 0) {
                answer += data[idx];
                idx -= lsb(idx);
            }
            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 = 0x3f3f3f3f;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        int val = T.query(mid);
        if (val == key) {
            int step = LOGSTEP;
            while (step > 0) {
                while (mid - step > 0 && T.query(mid - step) == key) {
                    mid -= step;
                }
                step >>= 1;
            }

            return mid;
        } else if (val < key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return -1;
}

int main()
{
    int n, m;

#ifdef LOCAL
    freopen("input", "r", stdin);
#else
    ifstream cin("aib.in");
    ofstream cout("aib.out");
#endif // LOCAL

    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;
}