#include <bits/stdc++.h>

using namespace std;

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

int n, m;
vector<int> a;

int lsb(int x) {
    return (x & (-x));
}

struct Aib {
    vector<int> v;

    void upd(int x, int poz) {
        while (poz <= n) {
            v[poz] += x;
            poz += lsb(poz);
        }
    }

    int sum(int poz) {
        int s = 0;
        while (poz) {
            s += v[poz];
            poz -= lsb(poz);
        }
        return s;
    }
} aib;

int caut(int k) {
    int st = 1, dr = n;
    while (st < dr) {
        int mij = (st + dr) / 2;
        int s = aib.sum(mij);
        // fout << st << " " << dr << "  " << mij << " " << s << "\n";
        if (s < k) {
            st = mij + 1;
        } else if (s > k) {
            dr = mij;
        } else {
            return mij;
        }
    }
    int s = aib.sum(dr);
    return (s == k ? dr : -1);
}

int main() {
    fin >> n >> m;
    a = vector<int>(n + 1);
    aib.v = vector<int>(n + 1);

    for (int i = 1; i <= n; i++) {
        fin >> a[i];
        aib.upd(a[i], i);
    }
    int t, x, y;
    for (int i = 0; i < m; i++) {
        fin >> t;
        if (t == 0) {
            fin >> x >> y;
            aib.upd(y, x);
        } else if (t == 1) {
            fin >> x >> y;
            int s = aib.sum(y) - aib.sum(x - 1);
            fout << s << "\n";
        } else {
            fin >> x;
            fout << caut(x) << "\n";
        }
    }
}