#import<fstream>
std::ifstream f("aib.in");
std::ofstream g("aib.out");
int A[100005],i=1,x,y,t,n,m,p,O;
int U(int i,int x){for(;i<=n;A[i]+=x,i+=(i&-i));}
int Q(int i){int R=0;for(;i;R+=A[i],i-=(i&-i));return R;}
main(){for(f>>n>>m;i<=n;i++){f>>x;U(i,x);}
while(m--){f>>t>>x;if(t==0){f>>y;U(x,y);}else if(t==1){f>>y;g<<Q(y)-Q(x-1)<<'\n';}
else{for(p=1;p<n;p*=2);for(i=O=0;p&&!O;p/=2){if(i+p>n)continue;if((y=Q(i+p))<=x)i+=p;if(y==x)O=1;}g<<(!O?-1:i)<<'\n';}}}