#include <bits/stdc++.h>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n,q;
vector<int> v;
vector<int> aib;

void update(int i,int number) {
    int dif = number - v[i];
    while(i <= n) {
        aib[i]+=number;
        i+= (i & (-i));
    }
}

int prefix_query(int i) {
    int sum = 0;
    while(i > 0) {
        sum+=aib[i];
        i-= i & (-i);
    }
    return sum;
}
int range_sum(int i,int j) {
    return prefix_query(j) - prefix_query(i-1);
}
int binary_searchx(int val)
{
    int i, step;
    for (step = 1; step < n; step <<= 1);
    for (i = 0; step; step >>= 1){
        if(val >= aib[i + step]){
            i+=step,val-=aib[i];
            if(!val) return i;
        }
    }
    return -1;
}
int main()
{
    fin >> n >> q;
    v.resize(n+1);
    aib.resize(n+1);
    for(int i = 1;i <= n;i++) {
        fin >> v[i];
        update(i,v[i]);
    }
    while(q--) {
        int type;
        fin >> type;
        if(type == 0) {
            int poz,val;
            fin >> poz >> val;
            update(poz,val);
        }else if(type == 1) {
            int i,j;
            fin >> i >> j;
            fout << range_sum(i,j) << '\n';
        }else {
            int k;
            fin >> k;
            int ans = binary_searchx(k);
            fout << ans << '\n';
        }
    }
    //fout << prefix_query(n);
    return 0;
}