#import<fstream>
int N,o,t,x,y,B['썐'],s,i;int U(int p){for(;N/p;p+=p&-p)B[p]+=x;}int Q(int p){for(x=0;p;p&=~-p)x+=B[p];return x;}main(){std::ifstream f("aib.in");std::ofstream g("aib.out");for(f>>N>>o;N/++y;U(y))f>>x;for(;f>>t>>y;){for(s=o=1;N/s;s*=2);for(i=0;o*s;s/=2)i+s>N|y<(x=Q(i+s))||(i+=s,o=x!=y);t<2&&f>>x;t?g<<(t&1?Q(x)-Q(y-1):o?-1:i)<<'\n',0:U(y);}}