#include<cstdio>
# define lsb(p)((-p)&p)
using namespace std;
int a,b,i,n,m,A[100010],x,t,s1,s2;
void update (int x, int p)
{
    for(int i=p;i<=n;i+=lsb(i))
        A[i]+=x;
}
int sum(int p){
    int suma=0;
    for(int i=p;i>0;i-=lsb(i))
        suma+=A[i];
    return suma;
}
int bs(int s){
    int st=1,dr=n,m;
    while(st<=dr){
        m=(st+dr)/2;
        int suma=sum(m);
        if(suma==s) return m;
        else if (s<suma)dr=m-1;
        else st=m+1;
    }
    return -1;
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i){
        scanf("%d",&x);
        update(x,i);
    }
    for(i=1;i<=m;i++){
        scanf("%d",&t);
        if(t==0){
            scanf("%d%d",&a,&b);
            update(b,a);
        }
        else if(t==1){
            scanf("%d%d",&a,&b);
            s1=sum(b);
            s2=sum(a-1);
            printf("%d\n",s1-s2);
        }
        else{
            scanf("%d",&a);
            int ok=bs(a);
            printf("%d\n",ok);
        }
    }

}