program bzoj3196;
const inf=;
maxn=;
maxm=; var n,m,time,temp:longint;
root,a:array [..maxn] of longint;
left,right,rnd,v,s,w:array [..maxm] of longint; procedure update(now:longint);
begin
s[now]:=s[left[now]]+s[right[now]]+w[now];
end; procedure rightturn(var now:longint);
var t:longint;
begin
t:=left[now];
left[now]:=right[t];
right[t]:=now;
s[t]:=s[now];
update(now);
now:=t;
end; procedure leftturn(var now:longint);
var t:longint;
begin
t:=right[now];
right[now]:=left[t];
left[t]:=now;
s[t]:=s[now];
update(now);
now:=t;
end; procedure insert(var now:longint; num:longint);
begin
if now= then
begin
inc(time);
now:=time;
w[now]:=;
s[now]:=w[now];
v[now]:=num;
rnd[now]:=random(inf);
exit;
end;
inc(s[now]);
if num=v[now] then inc(w[now])
else if num<v[now] then
begin
insert(left[now],num);
if rnd[left[now]]<rnd[now] then rightturn(now);
end
else
begin
insert(right[now],num);
if rnd[right[now]]<rnd[now] then leftturn(now);
end;
end; procedure del(var now:longint; num:longint);
begin
if v[now]=num then
begin
if w[now]> then
begin
dec(w[now]);
dec(s[now]);
exit;
end;
if left[now]*right[now]= then
now:=left[now]+right[now]
else
if rnd[left[now]]<rnd[right[now]] then
begin
rightturn(now);
del(now,num);
end
else
begin
leftturn(now);
del(now,num);
end
end
else
if num<v[now] then
begin
del(left[now],num);
dec(s[now]);
end
else
begin
del(right[now],num);
dec(s[now]);
end;
end; procedure build(now,l,r,x,num:longint);
var mid:longint;
begin
insert(root[now],num);
if l=r then exit;
mid:=(l+r) shr ;
if x<=mid then build(now<<,l,mid,x,num)
else build(now<< or ,mid+,r,x,num);
end; procedure ask_rank(now,num:longint);
begin
if now= then exit;
if num=v[now] then
begin
inc(temp,s[left[now]]);
exit;
end
else
if num<v[now] then
ask_rank(left[now],num)
else
begin
inc(temp,s[left[now]]+w[now]);
ask_rank(right[now],num);
end;
end; procedure get_rank(now,l,r,x,y,num:longint);
var mid:longint;
begin
mid:=(l+r) shr ;
if (l=x) and (r=y) then
begin
ask_rank(root[now],num);
exit;
end;
if mid>=y then get_rank(now<<,l,mid,x,y,num)
else if mid<x then get_rank(now<< or ,mid+,r,x,y,num)
else
begin
get_rank(now<<,l,mid,x,mid,num);
get_rank(now<< or ,mid+,r,mid+,y,num);
end;
end; procedure get_index(x,y,z:longint);
var l,r,ans,mid:longint;
begin
l:=; r:=inf;
while l<=r do
begin
mid:=(l+r) shr ;
temp:=;
get_rank(,,n,x,y,mid);
if temp<=z then
begin
l:=mid+;
ans:=mid;
end
else
r:=mid-;
end;
writeln(ans);
end; procedure change(now,l,r,x,num,y:longint);
var mid:longint;
begin
del(root[now],y);
insert(root[now],num);
if l=r then exit;
mid:=(l+r) shr ;
if x<=mid then change(now<<,l,mid,x,num,y)
else change(now<< or ,mid+,r,x,num,y);
end; function max(x,y:longint):longint;
begin
if x>y then exit(x)
else exit(y);
end; function min(x,y:longint):longint;
begin
if x<y then exit(x)
else exit(y);
end; procedure before(now,num:longint);
begin
if now= then exit;
if v[now]<num then
begin
temp:=max(v[now],temp);
before(right[now],num);
end
else
before(left[now],num);
end; procedure after(now,num:longint);
begin
if now= then exit;
if v[now]>num then
begin
temp:=min(v[now],temp);
after(left[now],num);
end
else
after(right[now],num);
end; procedure ask_after(now,l,r,x,y,num:longint);
var mid:longint;
begin
if (l=x) and (r=y) then
begin
after(root[now],num);
exit;
end;
mid:=(l+r) shr ;
if mid>=y then ask_after(now<<,l,mid,x,y,num)
else if mid<x then ask_after(now<< or ,mid+,r,x,y,num)
else
begin
ask_after(now<<,l,mid,x,mid,num);
ask_after(now<< or ,mid+,r,mid+,y,num);
end;
end; procedure ask_before(now,l,r,x,y,num:longint);
var mid:longint;
begin
if (l=x) and (r=y) then
begin
before(root[now],num);
exit;
end;
mid:=(l+r) shr ;
if mid>=y then ask_before(now<<,l,mid,x,y,num)
else if mid<x then ask_before(now<< or ,mid+,r,x,y,num)
else
begin
ask_before(now<<,l,mid,x,mid,num);
ask_before(now<< or ,mid+,r,mid+,y,num);
end;
end; procedure main;
var i,x,y,now,f:longint;
begin
read(n,m);
for i:= to n do read(a[i]);
for i:= to n do build(,,n,i,a[i]);
for i:= to m do
begin
read(f);
case f of
:
begin
read(x,y,now);
temp:=;
get_rank(,,n,x,y,now);
writeln(temp);
end;
:
begin
read(x,y,now);
get_index(x,y,now);
end;
:
begin
read(x,y);
change(,,n,x,y,a[x]);
a[x]:=y;
end;
:
begin
read(x,y,now);
temp:=;
ask_before(,,n,x,y,now);
writeln(temp);
end;
:
begin
read(x,y,now);
temp:=inf;
ask_after(,,n,x,y,now);
writeln(temp);
end;
end;
end;
end; begin
main;
end.