#include <bits/stdc++.h>
#define MAXN (1024 * 128)


using namespace std;

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

int aib[MAXN + 1];

int lsb(int x) {//lowest significant bit
    return x & (-x);
}

void update(int n, int poz, int val) {
    while (poz <= n) {
        aib[poz] += val;
        poz += lsb(poz);
    }
}
int query(int poz) {
    int rez = 0;

    while (poz > 0) {
        rez += aib[poz];
        poz -= lsb(poz);
    }
    return rez;
}

int main() {
    int n, m, i, t, a, b, nr, mask, sum, max_bit, bit;

    fin >> n >> m;
    for (i = 1; i <= n; i++) {
        fin >> nr;
        update(n, i, nr);
    }


    max_bit = 0;
    while ((1 << (max_bit + 1)) <= n) {
        max_bit++;
    }
    //printf("max_bit = %d\n", max_bit);
    for (i = 1; i <= m; i++) {
        fin >> t;
        if (t == 0) {
            fin >> a >> b;
            update(n, a, b);
        }else if (t == 1) {
            fin >> a >> b;
            fout << query(b) - query(a - 1) << "\n";
        }else {
            fin >> a;
            mask = sum = 0;
            for (bit = max_bit; bit >= 0; bit--) {
                //printf("sum + aib = %d, ind = %d\n", sum + aib[mask | (1 << bit)], mask | (1 << bit));
                if ((mask | (1 << bit)) <= n && sum + aib[mask | (1 << bit)] <= a) {
                    mask |= (1 << bit);
                    sum += aib[mask];
                }
            }
            if (sum != a) {
                fout << "-1\n";
            }else {
                fout << mask << "\n";
            }
        }
    }
    return 0;
}