#include <fstream>

using namespace std;

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

int sir[200001], poz , sf , elm,suma;

void aib(int i , int j , int pos){
    if(poz>(i+j)/2){
        sir[pos]+=elm;
        if(i==j)return;
        aib((i+j)/2+1,j,pos*2+1);
    }else
    if(poz<=(i+j)/2){
        sir[pos]+=elm;
        if(i==j)return;
        aib(i,(i+j)/2,pos*2);
    }
}

void caib(int i , int j , int pos){
    if(i>=poz&&j<=sf){
        suma+=sir[pos];
        return;
    }
    if(poz<=(i+j)/2){
        caib(i,(i+j)/2,pos*2);
    }
    if(sf>(i+j)/2){
        caib((i+j)/2+1,j,pos*2+1);
    }
}


void saib(int i , int j , int pos){
    if(poz==i){
    if(sir[pos]<=suma){
        poz=j+1;
        suma-=sir[pos];
        if(!suma)elm=j;
        return;
    }
    }else return;
    if(suma>0)
    saib(i,(i+j)/2,pos*2);
    if(suma>0)
    saib((i+j)/2+1,j,pos*2+1);
}

int main(){
    int n , m ;
    fi>>n>>m;
    for(int i=1;i<=n;i++){
    poz=i;
    fi>>elm;
    aib(1,n,1);
    }
    for(int i=1;i<=m;i++){
        int a,b;
        fi>>a;
        switch (a){
            case 0 :
            fi>>a>>b;
            poz=a;
            elm=b;
            aib(1,n,1);
            continue;
            case 1 :
            suma=0;
            fi>>a>>b;
            poz=a;
            sf=b;
            caib(1,n,1);
            fo<<suma<<'\n';
            continue;
            case 2:
            poz=1;
            fi>>a;
            elm=-1;
            suma=a;
            saib(1,n,1);
            fo<<elm<<'\n';
        }
    }
}