#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int i, n, m, aib[100001], v[100001], pos, st, dr, op;
long long sum, val;
int query(int x){
    int s = 0;
    while(x > 0){
        s = s + aib[x];
        x = x - (x & (-x));
    }
    return s;
}
void update(int x,int ad){
    while(x <= n){
        aib[x] += ad;
        x = x + (x & (-x));
    }
}
int cautbin(long long value){
    int st = 1, dr = n;
    while(st <= dr){
        int mid = (st + dr) / 2;
        int current = query(mid);
        if(current > value)
            dr = mid - 1;
        else if(current < value)
            st = mid + 1;
        else
            return mid;
    }
    return - 1;
}
int main()
{   f >> n >> m;
    for(i = 1; i <= n; i++){
        f >> v[i];
        update(i, v[i]);
    }
    for(i = 1; i <= m; i++){
        f >> op;
        if(op == 0){
            f >> pos >> val;
            update(pos, val);
        }
        else if(op == 1){
            f >> st >> dr;
            g << query(dr) - query(st - 1) << '\n';
        }
        else{
            f >> sum;
            g << cautbin(sum) << '\n';
        }
    }
    return 0;
}