#include <iostream>
#include <fstream>

using namespace std;

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

const int N_max = 100005;
int n, m;
int v[N_max], aib[N_max];
int least_se(int x){
    return (x ^ (x - 1)) & x;
}
void update(int poz, int val){
    for(int i = poz; i <= n; i += least_se(i))
        aib[i] += val;
}
int que(int poz){
    int sol = 0;
    for(int i = poz; i > 0; i -= least_se(i))
        sol += aib[i];
    return sol;
}
int find_least_m1(int x){
    int L = 0, R = n;
    while(L <= R){
        int mij = (L + R) /2;
        int sum = que(mij);
        if(sum == x)return mij;
        if(sum > x) R = mij - 1;
        else L = mij + 1;
    }
    return -1;
}
int find_least_m2(int x,int poz, int sum){
    int i;
    for(i = 0; poz + (1 << i) <= n && sum + aib[poz + (1 << i)] < x; i++);
    if(sum + aib[poz + (1 << i)] == x){return 1 << i;}
    if(i == 0 && sum + aib[poz + (1 << i)] > x) return -1 * (n + 100);
    i--;
    return (1 << i) + find_least_m2(x, poz + (1 << i), sum + aib[poz + (1 << i)]);

}

int main() {
    fin >> n >> m;
    for(int i = 1; i <= n; i++){
        fin >> v[i];
        update(i, v[i]);
    }
    while(m--){
        int tip; fin >> tip;
        switch (tip) {
            case 0:{
                int a, b; fin >> a >> b;
                update(a, b);
                break;
            }
            case 1:{
                int a, b; fin >> a >> b;
                fout << que(b) - que(a - 1) << '\n';
                break;
            }
            case 2:{
                int a; fin >> a;
                int x = find_least_m2(a,0 , 0);
                fout << (x < 0 ? -1 : x) << '\n';
            }
        }
    }
}