#include <bits/stdc++.h>
#define Nmax 1000005

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");
int v[Nmax],A[Nmax],n,m;
int poz,start,stop;

void update(int poz, int val){
    while(poz<=n){
    A[poz]+=val;
    poz+=(poz&(-poz));
    }
}

void citire(){
    fin>>n>>m;
    for(int i=1,x;i<=n;i++){
        fin>>x;
        update(i,x);
        }
}


int query(int poz){
    int sum=0;
    while(poz>0){
        sum+=A[poz];
        poz-=(poz&(-poz));
    }
    return sum;
}

int caut(int k){
    int l=1,r=n,mid,val;
    while(l<=r){
        mid=(l+r)/2;
    val=query(mid);
    if(val==k)return mid;
    if(val<k) l=mid+1;
    else r=mid-1;

    }
    return -1;
}

void rezolvare(){
    citire();
    int op,x,y,k;
    for(int i=1;i<=m;i++){
        fin>>op;
        if(op==0){
            fin>>x>>y;
            update(x,y);
        }
        else if(op==1){
            fin>>x>>y;
            fout<<query(y)-query(x-1)<<"\n";
        }
        else {
            fin>>k;
            fout<<caut(k)<<"\n";
        }
    }
}

int main()
{
    rezolvare();

    return 0;
}