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

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

#define NMAX 100005
#define lsb(x) ((-x) & (x))

int N, M, aib[NMAX], tip, x, y;

void update(int pos, int value) {
    while (pos <= N) {
        aib[pos] += value;
        pos += lsb(pos);
    }
}

int query(int pos) {
    int res = 0;
    while (pos) {
        res += aib[pos];
        pos -= lsb(pos);
    }

    return res;
}

int main() {
    f >> N >> M;
    for (int i = 1; i <= N; ++i) {
        f >> x;
        update(i, x);
    }
    while (M--) {
        f >> tip >> x;
        if (tip == 0) {
            f >> y;
            update(x, y);
        } else if (tip == 1) {
            f >> y;
            g << query(y) -  query(x - 1) << '\n';
        } else {
            int pos = 0;
            for (int pas = (1 << 30); pas; pas >>= 1) {
                if (pos +pas <= N && query(pos + pas) <= x) {
                    pos += pas;
                }
            }

            if (query(pos) != x) {
                g << -1 << '\n';
            } else {
                g << pos << '\n';
            }
        }
    }
    return 0;
}