#include <fstream>
#define IN "aib.in"
#define OUT "aib.out"
#define DMAX 100008
#define PUTERI 17
#define p2mare(x) ((x ^ (x - 1) & x))
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

int n, m;
int v[DMAX];
int f[DMAX];

void citire();
int suma(int);
void update(int, int);
int poz_suma(int);//pozitia minima cu suma x

int main(int argc, const char * argv[]){
    citire();
    return 0;
}

int poz_suma(int x){
    int p=1, u=n, mid, val;
    while(p<=u){
        mid=(p+u)>>1;
        val=suma(mid);
        if(val==x)
            return mid;
        else{
            if(val>x)
                u=mid-1;
            else
                p=mid+1;
        }
    }
    return -1;
}
int suma(int p){
    int sum=0, aux;
    for (aux=p; aux>0; aux-=p2mare(aux))
        sum+=f[aux];
    
    return sum;
}

void update(int p, int val){
    int aux;
    for (aux=p; aux<=n; aux+=p2mare(aux))
        f[aux]+=val;
}

void citire(){
    fin >>n>>m;
    
    int i;
    for (i=1; i<=n; ++i){
        fin >>v[i];
        update(i, v[i]);
    }
    
    int x, y, tip;
    for (i=1; i<=m; ++i){
        fin >>tip;
        switch (tip) {
            case 0:
                fin >>x>>y;
                update(x, y);
                break;
            case 1:
                fin >>x>>y;
                fout <<suma(y)-suma(x-1)<<'\n';
                break;
            case 2:
                fin >>x;
                fout <<poz_suma(x)<<'\n';
                break;
        }
    }
}