#include <cstdio>
#define zeros(x) ((x)&(-x))
using namespace std;
int n,m,aib[100003];
void add(int x,int qun){
int i;
for(i=x;i<=n;i+=zeros(i))
aib[i]+=qun;
}
int sum(int x){
int i,nr;nr=0;
for(i=x;i>0;i-=zeros(i))
nr+=aib[i];
return nr;
}
int binar(int x,int y,int k)
{int mij;
if(sum(x)==k)return x;
if(sum(y)==k)return y;
while(x<=y){
mij=(x+y)/2;
if(sum(mij)==k)return mij;
else if(sum(mij)<k)x=mij+1;
else if(sum(mij)>k)y=mij-1;
}
return -1;
}
int i,x,y,z;
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);
add(i,x);
}
for(i=1;i<=m;i++){
scanf("%d",&z);
if(z==0){
scanf("%d %d",&x,&y);
add(x,y);}
if(z==1){
scanf("%d %d",&x,&y);
printf("%d\n",sum(y)-sum(x-1));}
if(z==2){
scanf("%d",&x);
printf("%d\n",binar(1,n,x));
}
}

    return 0;
}