#include <iostream>
#include <fstream>

using namespace std;

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

#define zeroes(x) ((x ^ (x - 1)) & x)

int n,m;
int *v;
int *AIB;

void Add(int x, int quantity){
    int i;
    for(i=x; i<=n; i+= zeroes(i)){
        AIB[i] += quantity;
    }
}

int Compute(int x){
    int i,ret=0;
    for(i=x; i>0; i-= zeroes(i)){
        ret += AIB[i];
    }
    return ret;
}

int BS(int a, int liminf, int limsup){
    if(limsup <= liminf) return -1;
    int mij = (limsup + liminf) / 2;
    int suma = Compute(mij);
    if(suma == a){
        return mij;
    }else if(suma < a){
        return BS(a, mij+1, limsup);
    }else{
        return BS(a,liminf, mij);
    }
}

int main()
{
    int opcode, a, b, i, j;
    f>>n>>m;
    v = new int[n+1];
    AIB = new int[n+1];
    for(i=0; i<=n; i++){
        AIB[i] = 0;
    }
    for(i=1 ; i<=n ; i++){
        f>>v[i];
        Add(i, v[i]);
//        for(j = 1 ; j <= n ;j++){
//            cout<<AIB[j]<<' ';
//        }
//        cout<<'\n';
    }
    for(i=1 ; i<=m ; i++){
        f>>opcode;
        if(opcode == 0){
            f>>a>>b;
            Add(a, b);
        }else if(opcode == 1){
            f>>a>>b;
            g<<Compute(b) - Compute(a-1)<<'\n';
        }else{
            f>>a;
            g<<BS(a, 0, n)<<'\n';
        }
    }
    delete []v;
    delete []AIB;
    f.close();
    g.close();
    return 0;
}