program bzoj3196;const inf=100000000;    maxn=200001;    maxm=3000001;var n,m,time,temp:longint;    root,a:array [0..maxn] of longint;    left,right,rnd,v,s,w:array [0..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=0 then     begin      inc(time);      now:=time;      w[now]:=1;      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]>1 then         begin          dec(w[now]);          dec(s[now]);          exit;        end;      if left[now]*right[now]=0 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 1;  if x<=mid then build(now<<1,l,mid,x,num)  else build(now<<1 or 1,mid+1,r,x,num);end;procedure ask_rank(now,num:longint);begin  if now=0 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 1;  if (l=x) and (r=y) then     begin       ask_rank(root[now],num);      exit;    end;  if mid>=y then get_rank(now<<1,l,mid,x,y,num)  else if mid<x then get_rank(now<<1 or 1,mid+1,r,x,y,num)  else    begin      get_rank(now<<1,l,mid,x,mid,num);      get_rank(now<<1 or 1,mid+1,r,mid+1,y,num);    end;end;procedure get_index(x,y,z:longint);var l,r,ans,mid:longint;begin  l:=0; r:=inf;  while l<=r do    begin      mid:=(l+r) shr 1;      temp:=1;      get_rank(1,1,n,x,y,mid);      if temp<=z then         begin          l:=mid+1;          ans:=mid;        end      else         r:=mid-1;    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 1;  if x<=mid then change(now<<1,l,mid,x,num,y)  else change(now<<1 or 1,mid+1,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=0 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=0 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 1;  if mid>=y then ask_after(now<<1,l,mid,x,y,num)  else if mid<x then ask_after(now<<1 or 1,mid+1,r,x,y,num)  else     begin      ask_after(now<<1,l,mid,x,mid,num);      ask_after(now<<1 or 1,mid+1,r,mid+1,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 1;  if mid>=y then ask_before(now<<1,l,mid,x,y,num)  else if mid<x then ask_before(now<<1 or 1,mid+1,r,x,y,num)  else     begin      ask_before(now<<1,l,mid,x,mid,num);      ask_before(now<<1 or 1,mid+1,r,mid+1,y,num);    end;end;procedure main;var i,x,y,now,f:longint;begin  read(n,m);  for i:=1 to n do read(a[i]);  for i:=1 to n do build(1,1,n,i,a[i]);  for i:=1 to m do    begin      read(f);      case f of         1:          begin            read(x,y,now);            temp:=1;            get_rank(1,1,n,x,y,now);            writeln(temp);          end;        2:          begin            read(x,y,now);            get_index(x,y,now);          end;        3:          begin            read(x,y);            change(1,1,n,x,y,a[x]);            a[x]:=y;          end;        4:          begin            read(x,y,now);            temp:=0;            ask_before(1,1,n,x,y,now);            writeln(temp);          end;        5:          begin            read(x,y,now);            temp:=inf;            ask_after(1,1,n,x,y,now);            writeln(temp);          end;      end;    end;end;begin  main;end.