#include <stdio.h>
using namespace std;
int b,p,a,i,v[1001*1001],n,aib[1001*1001];

int sol(int x){
int i;
int rez=0;
for(i=x;i>0;i-=(i&(-i)))
    rez+=aib[i];
return rez;

}
void add(int x,int val,int n){
int i;
for(i=x;i<=n;i+=(i&(-i))) aib[i]+=val;

}
int ok=0;
int cautbin(int x,int st,int dr){
int mij=(st+dr)/2;
if(dr!=st){int wow=sol(mij);
   if(wow>x) return cautbin(x,st,mij);
   else if(wow<x) return cautbin(x,mij+1,dr);
    else return mij;

}
if(sol(mij)==x) return mij;
else return -1;

}

int main()
{

   freopen("aib.in","r",stdin);
   freopen("aib.out","w",stdout);
   int n,m;
   scanf("%d%d",&n,&m);
   for(i=1;i<=n;i++){scanf("%d",&v[i]);
   add(i,v[i],n);

   }
   for(i=1;i<=m;i++){
    scanf("%d",&p);
    if(p==0){
        scanf("%d%d",&a,&b);
        add(a,b,n);

    }
    else if(p==1){
        scanf("%d%d",&a,&b);
        printf("%d\n",sol(b)-sol(a-1));

    }
    else {
        scanf("%d",&a);
        printf("%d\n",cautbin(a,1,n));
    }



   }
    return 0;
}