#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
#define C 1<<17
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 c=C,d=0;
    while(c>>=1) if(c+d<=n&&q(c+d)<=v)d+=c;
    return q(d)==v?d:-1;
    }
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;
    }