#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<long int> suma;
void adauga(long int i,long int n,long int max){
    while(i<=max){
        suma[i]+=n;
        i+=(i&(-i));
    }
}
long int sum(long int i){
    long int n=0;

    while(i>0){
        n+=suma[i];
        i-=(i&(-i));
    }
    return n;
}
long int minim(long int a,long int max){
    long int i=0;
    long int p=1;
    while(p<=max)p*=2;
    p/=2;

    while(i+p<=max and p){
        long int mid=i+p;
        if(suma[mid]==a) return mid;
        else if(suma[mid]<a){
            i=mid;
            a-=suma[mid];
        }
        p/=2;
    }
    if(a!=0) return -1;
    else return i;
}

int main(){
    ifstream in("aib.in");
    ofstream out("aib.out");


    long int n,m;
    in>>n>>m;suma=vector<long int>(n+1,0);


    for(long int i=0;i<n;i++){
        long int temp;
        in>>temp;
        adauga(i+1,temp,n);
    }
    for(long int i=0;i<m;i++){
        long int c;
        in>>c;
        switch(c){
            long int a,b;
            case 0:
            in>>a>>b;
            adauga(a,b,n);
            break;
            case 1:
            in>>a>>b;
            out<<sum(b)-sum(a-1)<<"\n";
            break;
            case 2:
            in>>a;
            out<<minim(a,n)<<"\n";
            break;
        }
    }

}