#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 50001
#define SQRT 227
int n,m,xs[N],ys[N],ks[N],op[N],en,ma[100001],en2,a[100001];
int num[N],l[SQRT],r[SQRT],sumv[SQRT],sum=1;//分块
int num2[100001],l2[320],r2[320],tot=1;//函数式权值分块
struct Point{int v,p;}t[100001];
bool operator < (const Point &a,const Point &b){return a.v<b.v;}
struct Val_Block
{
int b[100001],sumv[320];
void Insert(const int &x){++b[x]; ++sumv[num2[x]];}
void Delete(const int &x){--b[x]; --sumv[num2[x]];}
}T[SQRT],S;
void makeblock()
{
int sz=sqrt(n);
if(!sz) sz=1;
for(;sum*sz<n;++sum)
{
l[sum]=r[sum-1]+1;
r[sum]=sum*sz;
for(int i=l[sum];i<=r[sum];++i)
num[i]=sum;
}
l[sum]=r[sum-1]+1;
r[sum]=n;
for(int i=l[sum];i<=r[sum];++i)
num[i]=sum;
}
void val_mb()
{
int sz=sqrt(en2);
if(!sz) sz=1;
for(;tot*sz<en2;++tot)
{
l2[tot]=r2[sum-1]+1;
r2[tot]=tot*sz;
for(int i=l2[tot];i<=r2[tot];++i)
num2[i]=tot;
}
l2[tot]=r2[sum-1]+1;
r2[tot]=en2;
for(int i=l2[tot];i<=r2[tot];++i)
num2[i]=tot;
}
void Init_Ts()
{
for(int i=1;i<=sum;++i)
{
T[i]=T[i-1];
for(int j=l[i];j<=r[i];++j)
T[i].Insert(a[j]);
}
}
int Kth(const int &L,const int &R,const int &x)
{
int cnt=0,res;
if(num[L]+1>=num[R])
{
for(int i=L;i<=R;++i)
S.Insert(a[i]);
for(int i=1;;++i)
{
cnt+=S.sumv[i];
if(cnt>=x)
{
cnt-=S.sumv[i];
for(int j=l2[i];;++j)
{
cnt+=S.b[j];
if(cnt>=x)
{
res=j;
goto OUT2;
}
}
}
}
OUT2:for(int i=L;i<=R;++i)
S.Delete(a[i]);
return res;
}
for(int i=L;i<=r[num[L]];++i)
S.Insert(a[i]);
for(int i=l[num[R]];i<=R;++i)
S.Insert(a[i]);
int LB=num[L],RB=num[R]-1;
for(int i=1;;++i)
{
cnt+=(T[RB].sumv[i]-T[LB].sumv[i]+S.sumv[i]);
if(cnt>=x)
{
cnt-=(T[RB].sumv[i]-T[LB].sumv[i]+S.sumv[i]);
for(int j=l2[i];;++j)
{
cnt+=(T[RB].b[j]-T[LB].b[j]+S.b[j]);
if(cnt>=x)
{
res=j;
goto OUT;
}
}
}
}
OUT:for(int i=L;i<=r[num[L]];++i)
S.Delete(a[i]);
for(int i=l[num[R]];i<=R;++i)
S.Delete(a[i]);
return res;
}
int Rank(const int &L,const int &R,const int &x)
{
int cnt=0;
if(num[L]+1>=num[R])
{
for(int i=L;i<=R;++i)
S.Insert(a[i]);
for(int i=1;i<num2[x];i++)
cnt+=S.sumv[i];
for(int i=l2[num2[x]];i<x;i++)
cnt+=S.b[i];
for(int i=L;i<=R;++i)
S.Delete(a[i]);
return cnt+1;
}
for(int i=L;i<=r[num[L]];++i)
S.Insert(a[i]);
for(int i=l[num[R]];i<=R;++i)
S.Insert(a[i]);
int LB=num[L],RB=num[R]-1;
for(int i=1;i<num2[x];i++)
cnt+=(T[RB].sumv[i]-T[LB].sumv[i]+S.sumv[i]);
for(int i=l2[num2[x]];i<x;i++)
cnt+=(T[RB].b[i]-T[LB].b[i]+S.b[i]);
for(int i=L;i<=r[num[L]];++i)
S.Delete(a[i]);
for(int i=l[num[R]];i<=R;++i)
S.Delete(a[i]);
return cnt+1;
}
int f,c;
inline void R(int &x){
c=0;f=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c>='0'&&c<='9';c=getchar())(x*=10)+=(c-'0');
x*=f;
}
void P(int x){
if(x<10)putchar(x+'0');
else{P(x/10);putchar(x%10+'0');}
}
int Next(const int &L,const int &R,const int &x)
{
int res;
if(num[L]+1>=num[R])
{
for(int i=L;i<=R;++i)
S.Insert(a[i]);
for(int i=x+1;i<=r2[num2[x]];i++)
if(S.b[i])
{
res=i;
goto OUT2;
}
for(int i=num2[x]+1;;i++)
if(S.sumv[i])
for(int j=l2[i];;j++)
if(S.b[j])
{
res=j;
goto OUT2;
}
OUT2:for(int i=L;i<=R;++i)
S.Delete(a[i]);
return res;
}
for(int i=L;i<=r[num[L]];++i)
S.Insert(a[i]);
for(int i=l[num[R]];i<=R;++i)
S.Insert(a[i]);
int LB=num[L],RB=num[R]-1;
for(int i=x+1;i<=r2[num2[x]];i++)
if((T[RB].b[i]-T[LB].b[i]+S.b[i]))
{
res=i;
goto OUT;
}
for(int i=num2[x]+1;;i++)
if((T[RB].sumv[i]-T[LB].sumv[i]+S.sumv[i]))
for(int j=l2[i];;j++)
if((T[RB].b[j]-T[LB].b[j]+S.b[j]))
{
res=j;
goto OUT;
}
OUT:for(int i=L;i<=r[num[L]];++i)
S.Delete(a[i]);
for(int i=l[num[R]];i<=R;++i)
S.Delete(a[i]);
return res;
}
int Pre(const int &L,const int &R,const int &x)
{
int res;
if(num[L]+1>=num[R])
{
for(int i=L;i<=R;++i)
S.Insert(a[i]);
for(int i=x-1;i>=l2[num2[x]];i--)
if(S.b[i])
{
res=i;
goto OUT2;
}
for(int i=num2[x]-1;;i--)
if(S.sumv[i])
for(int j=r2[i];;j--)
if(S.b[j])
{
res=j;
goto OUT2;
}
OUT2:for(int i=L;i<=R;++i)
S.Delete(a[i]);
return res;
}
for(int i=L;i<=r[num[L]];++i)
S.Insert(a[i]);
for(int i=l[num[R]];i<=R;++i)
S.Insert(a[i]);
int LB=num[L],RB=num[R]-1;
for(int i=x-1;i>=l2[num2[x]];i--)
if((T[RB].b[i]-T[LB].b[i]+S.b[i]))
{
res=i;
goto OUT;
}
for(int i=num2[x]-1;;i--)
if((T[RB].sumv[i]-T[LB].sumv[i]+S.sumv[i]))
for(int j=r2[i];;j--)
if((T[RB].b[j]-T[LB].b[j]+S.b[j]))
{
res=j;
goto OUT;
}
OUT:for(int i=L;i<=r[num[L]];++i)
S.Delete(a[i]);
for(int i=l[num[R]];i<=R;++i)
S.Delete(a[i]);
return res;
}
int main()
{
R(n);
R(m);
makeblock();
en=n;
for(int i=1;i<=n;++i)
R(t[i].v),
t[i].p=i;
for(int i=1;i<=m;++i)
{
R(op[i]);
if(op[i]==3)
R(xs[i]),R(ks[i]);
else
R(xs[i]),R(ys[i]),R(ks[i]);
if(op[i]!=2)
t[++en].v=ks[i],
t[en].p=en;
}
sort(t+1,t+en+1);
ma[a[t[1].p]=++en2]=t[1].v;
for(int i=2;i<=en;++i)
{
if(t[i].v!=t[i-1].v)
++en2;
ma[a[t[i].p]=en2]=t[i].v;
}
val_mb();
Init_Ts();
en=n;
for(int i=1;i<=m;++i)
{
if(op[i]!=2)
++en;
if(op[i]==3)
{
for(int j=num[xs[i]];j<=sum;++j)
T[j].Delete(a[xs[i]]),T[j].Insert(a[en]);
a[xs[i]]=a[en];
}
else if(op[i]==2)
P(ma[Kth(xs[i],ys[i],ks[i])]),puts("");
else if(op[i]==1)
P(Rank(xs[i],ys[i],a[en])),puts("");
else if(op[i]==4)
P(ma[Pre(xs[i],ys[i],a[en])]),puts("");
else
P(ma[Next(xs[i],ys[i],a[en])]),puts("");
}
return 0;
}