#include <stdio.h>
#define t(i) i&(i^(i-1))
#define fr(i,a,b) for(int i=a;i<=b;++i)
#define N 100000
int a[N+1],n,m,x,y;
void u(int p,int v){
    while(p<=n){a[p]+=v;p+=t(p);}
    }
int q(int p){
    int s=0;
    while(p){s+=a[p];p-=t(p);}
    return s;
    }
int s(int v){
    int p=1,c;
    if(a[1]==v)return 1;
    while(v){
        c=1;
        while(p+c<=n&&a[p+c]<=v)p+=c,c<<=1;
        if(c==1)return -1;
        v-=a[p];
        }
    return p;
    }
int main(){
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%i%i",&n,&m);
    fr(i,1,n)scanf("%i",&x),u(i,x);
    fr(i,1,m){
        scanf("%i%i",&x,&y);
        if(!x)scanf("%i",&x),u(y,x);
        else if(x==1) scanf("%i",&x),printf("%i\n",q(x)-q(y-1));
        else printf("%i\n",s(y));
        }
    return 0;
    }