#include <fstream>

using namespace std;

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

const int NMAX = 100005;
int N, M;
int AIB[NMAX];

inline int zeros(int x){
    return (((x ^ (x - 1)) & x));
}

void Update(int position, int increment){
    for(int i = position; i <= N ; i += zeros(i))
        AIB[i] += increment; 
}

int Compute(int node){
    int sum = 0;
    for(int i = node; i >= 1 ; i -= zeros(i))
        sum += AIB[i];
    return sum;
}

int Search(int k){
    int i;
    for(i = 1; i < N; i <<= 1);
    
    for(int power = i, add = 0; power >= 1; power >>= 1){
        if(power + add <= N){
            if(AIB[power + add] <= k){
                add += power;
                k -= AIB[add];
                if(!k) return add;
            }
        } 
    }
    return -1;
}


int main(){
    in >> N >> M;
    for(int i = 1; i <= N; ++i){
        int nr;
        in >> nr;
        Update(i, nr);
    }
    while(M){
        int o, a, b;
        in >> o >> a;
        if(o == 0){
            in >> b;
            Update(a, b);
        }
        else if(o == 1){
            in >> b;
            out << Compute(b) - Compute(a - 1) << "\n";
        }
        else
            out << Search(a) << "\n";
        M--;
    }
    return 0;
}