#include <fstream>

using namespace std;

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

const int mxN = 1e5 + 1;

unsigned int aib[mxN], n, m;

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

unsigned int query(int ind){
    unsigned int ans = 0;
    while(ind){
        ans += aib[ind];
        ind -= ind & (-ind);
    }
    return ans;
}

int cautBin(unsigned int target) {
    int pos = 0;
    unsigned int original = target;
    for (int step = (1 << 17); step > 0; step >>= 1) {
        if (pos + step <= n && aib[pos + step] < target) {
            target -= aib[pos + step];
            pos += step;
        }
    }
    pos++;
    if (pos > n || query(pos) != original) return -1;
    return pos;
}

int main(){
    unsigned int aux;
    fin >> n >> m;
    for(int i = 1; i <= n; i++){
        fin >> aux;
        update(i, aux);
    }

    for(int i =1 ; i <= m; i++){
        unsigned int c, a, b;
        fin >> c >> a;
        if(c == 0){
            fin >> b;
            update(a, b);
        }else if(c == 1){
            fin >> b;
            fout << query(b) - query(a - 1) << "\n";
        }else{
            fout << cautBin(a) << "\n";
        }
    }
}