#import<fstream>
std::ifstream f("aib.in");
std::ofstream g("aib.out");
int arb[100005],i=1,x,y,t,n,m,p,ok;
int U(int i,int x){for(;i<=n;arb[i]+=x,i+=(i&-i));}
int Q(int i){if(i>n)return -1;int sol=0;for(;i;sol+=arb[i],i-=(i&-i));return sol;}
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=ok=0;p&&!ok;p/=2){if((y=Q(i+p))<=x)i+=p;if(y==x)ok=1;}g<<(!ok?-1:i)<<'\n';}}}