#include <fstream>
#include <cmath>

using namespace std;

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

const int Nmax = 100005;

int n, log2_n, q;
int aib[Nmax];

void aib_update(int poz, int val){
    for(int i = poz; i <= n; i += (i & (-i))){
        aib[i] += val;
    }
}

int aib_query(int poz){
    int sum = 0;

    for(int i = poz; i >= 1; i -= (i & (-i))){
        sum += aib[i];
    }

    return sum;
}

int aib_query_interval(int capat_st, int capat_dr){
    return aib_query(capat_dr) - aib_query(capat_st - 1);
}

int aib_caut_bin(int val){
    int poz = 0, sum = 0;
    for(int putere = log2_n; putere >= 0 && (poz ^ (1 << putere)) <= n; putere--){
        if(sum + aib[(poz ^ (1 << putere))] <= val){
            sum += aib[(poz ^ (1 << putere))];
            poz ^= (1 << putere);
        }
    }

    if(sum == val){
        return poz;
    }
    return -1;
}

void citire(){
    int val;

    fin >> n >> q;
    log2_n = log2(n);

    for(int i = 1; i <= n; i++){
        fin >> val;
        aib_update(i, val);
    }
}

void citire_si_rezolvare_interogari(){
    int tip, capat_st, capat_dr, pozitie, val;

    for(int i = 1; i <= q; i++){
        fin >> tip;
        if(tip == 0){
            fin >> pozitie >> val;
            aib_update(pozitie, val);
        }
        else if(tip == 1){
            fin >> capat_st >> capat_dr;
            fout << aib_query_interval(capat_st, capat_dr) << '\n';
        }
        else{
            fin >> val;
            fout << aib_caut_bin(val) << '\n';
        }
    }
}

int main(){
    citire();
    citire_si_rezolvare_interogari();

    return 0;
}