#include <fstream>
#define nzero(x) ((x^(x-1))&x)

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int n, m, i, j, c, x, y;
int arb[100005];

int sum(int x) {
    int i, s = 0;
    for (i = x; i >=1; i -= nzero(i))
        s += arb[i];
    return s;
}

void update(int x, int k) {
    int i;
    for (i = x; i <= n; i += nzero(i))
        arb[i] += k;
}

int cb(int x) {
    int st = 1, dr = n, m, k;
    while (st <= dr) {
        m = (st+dr)/2;
        k = sum(m);
        if (k <= x)
            st = m+1;
        else dr = m-1;
    }
    k = sum(dr);
    if (k < x)
        dr++;
    if (sum(dr) == x)
        return dr;
    else return -1;
    //g << dr << ' ';
}

int main() {
    f >> n >> m;
    for (i = 1; i <= n; i++) {
        f >> x;
        update(i, x);
    }
    for (i = 1; i <= m; i++) {
        f >> c >> x;
        if (c == 0 || c == 1) {
            f >> y;
            if (c == 1)
                g << sum(y)-sum(x-1) << '\n';
            else update(x, y);
            continue;
        }
        g << cb(x) <<'\n';
    }
    return 0;
}