#include<bits/stdc++.h>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

#define LEN 131072

int aib[LEN + 1];

void update(int poz, int x) {
    int p = 1;
    while(poz <= LEN) {
        if(p & poz) {
            aib[poz] += x;
            poz = poz + p;
        }
        p = p * 2;
    }
}

int get_sum(int poz) {
    int p = 1;
    int sum = 0;
    while(poz > 0) {
        if(p & poz) {
            sum = sum + aib[poz];
            poz = poz - p;
        }
        p = p * 2;
    }
    return sum;
}

int get_poz(int k) {
    int poz = 0, sum = 0;
    for(int p = LEN; p >= 1; p = p / 2) {
        if(aib[poz + p] + sum <= k) {
            poz = poz + p;
            sum = sum + aib[poz];
        }
    }
    if(aib[poz] != k) {
        return -1;
    } else {
        return poz;
    }
}

int main() {
    int n, q;
    fin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        update(i, x);
    }
    for(int i = 1; i <= q; i++) {
        int op;
        fin >> op;
        if(op == 0) {
            int a, b;
            fin >> a >> b;
            update(a, b);
        } else if(op == 1) {
            int a, b;
            fin >> a >> b;
            fout << get_sum(b) - get_sum(a - 1) << "\n";
        } else {
            int k;
            fin >> k;
            fout << get_poz(k) << "\n";
        }
    }
}