#include <iostream>
#include <fstream>

using namespace std;

#define nmax 100005

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

int n, m, aib[nmax];

void udpate(int poz, int val){

    int bit = 0;

    for(; poz<=n; ){
        while( (poz & (1<<bit))==0 ) ++bit;//caut primul bit de 1
        aib[poz] += val;
        poz += (1<<bit); //adaug cel mai nesemnificativ bit(mutandu-l cu o pozitie mai la stanga);
        ++bit;
    }

}

void citeste(){

    f >> n >> m;
    for(int i=1; i<=n; i++){
        int x;
        f >> x;
        udpate(i,x);
    }

    for(int i=1; i<=n; i++) cout << aib[i] << " " ;

}

int query(int poz){

    int sum=0, bit=0;
    for(; poz; ){
        sum += aib[poz];
        while( (poz & (1<<bit)) == 0) ++bit;//caut primul bit de 1
        poz -= (1<<bit);//elimin cel mai nesemnificativ bit de 1
        ++bit;
    }

    return sum;

}

int cb(int val){

    int st = 0;
    int dr = n;
    int sol = -1;

    while(st <= dr){
        int mij = (st + dr) / 2;
        if (query(mij) >= val){
            sol = mij;
            dr = mij - 1;
        }else st = mij + 1;
    }

    return sol;

}

void rezolva(){

    for(int i=1; i<=m; i++){
        int tip, x, y;
        f >> tip;
        if (tip == 0){
            f >> x >> y;
            udpate(x, y);
            continue;
        }
        if (tip == 1){
            f >> x >> y;
            g << query(y) - query(x-1) << "\n";
            continue;
        }
        if (tip == 2){
            f >> x;
            g << cb(x) << "\n";
        }
    }

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;

}