#include <bits/stdc++.h>
using namespace std;

const int N=100005;
const int M=335;
const int K=245;

int n,m,len,len2,bk,bk2;
int arr[N];
int cnt[K][N];
int pre[K][N];
int seg[K][M];
int fir[K][N];
int p[N];
int asi[M];
int bkt[N];

int get(int x) {
    return (x-1)/len;
}

int getl(int x) {
    return x*len+1;
}

int getr(int x) {
    return (x+1)*len;
}

int get2(int x) {
    return (x-1)/len2;
}

int getl2(int x) {
    return x*len2+1;
}

int getr2(int x) {
    return (x+1)*len2;
}

int find(int x) {
    if (p[x]==x) return x;
    else return p[x]=find(p[x]);
}

void init() {
    for (int i=1;i<=n;++i) {
        cnt[get(i)][arr[i]]++;
        // printf("cnt[%d][%d] = %d\n",get(i),arr[i],cnt[get(i)][arr[i]]);
    }
    for (int i=0;i<bk;++i) {
        for (int j=1;j<=n;++j) {
            if (i==0) {
                pre[i][j]=cnt[i][j];
                continue;
            }
            pre[i][j]=cnt[i][j]+pre[i-1][j];
            // printf("pre[%d][%d] = %d\n",i,j,pre[i][j]);
        }
    }
    for (int i=1;i<=n;++i) {
        seg[get(i)][get2(arr[i])]++;
        // printf("seg[%d][%d] = %d\n",get(i),get2(arr[i]),seg[get(i)][get2(arr[i])]);
    }
    for (int i=1;i<bk;++i) {
        for (int j=0;j<bk2;++j) {
            seg[i][j]+=seg[i-1][j];
        }
    }
    for (int i=1;i<=n;++i) {
        if (!fir[get(i)][arr[i]]) {
            fir[get(i)][arr[i]]=i;
        }
        p[i]=fir[get(i)][arr[i]];
    }
}

void modify(int l,int r,int x,int y) {
    if (get(l)==get(r)) {
        int chgcnt=0;
        for (int i=getl(get(l));i<=getr(get(l));++i) {
            arr[i]=arr[find(i)];
        }
        for (int i=l;i<=r;++i) {
            if (arr[i]==x) {
                arr[i]=y;
                chgcnt++;
            }
        }
        cnt[get(l)][y]+=chgcnt;
        cnt[get(l)][x]-=chgcnt;
        fir[get(l)][x]=0;
        fir[get(l)][y]=0;
        for (int i=getl(get(l));i<=getr(get(l));++i) {
            if (arr[i]!=x && arr[i]!=y) continue;
            if (!fir[get(i)][arr[i]]) {
                fir[get(i)][arr[i]]=i;
            }
            p[i]=fir[get(i)][arr[i]];
        }
        for (int i=get(l);i<bk;++i) {
            seg[i][get2(y)]+=chgcnt;
            seg[i][get2(x)]-=chgcnt;
            pre[i][y]+=chgcnt;
            pre[i][x]-=chgcnt;
        }
    } else {
        modify(l,getr(get(l)),x,y);
        modify(getl(get(r)),r,x,y);
        int yadd=0;
        int xadd=0;
        for (int i=get(l)+1;i<=get(r)-1;++i) {
            if (fir[i][x]) {
                if (fir[i][y]) p[fir[i][x]]=fir[i][y];
                else fir[i][y]=fir[i][x],arr[fir[i][x]]=y;
                fir[i][x]=0;
                yadd+=cnt[i][x];
                xadd+=-cnt[i][x];
                cnt[i][y]+=cnt[i][x];
                cnt[i][x]-=cnt[i][x];
            }
            seg[i][get2(y)]+=yadd;
            seg[i][get2(x)]+=xadd;
            pre[i][y]+=yadd;
            pre[i][x]+=xadd;
        }
    }
}

int query(int l,int r,int k) {
    // cout<<"QUERY: "<<l<<" "<<r<<" "<<k<<endl;
    if (get(l)==get(r)) {
        memset(asi,0,sizeof(asi));
        memset(bkt,0,sizeof(bkt));
        for (int i=l;i<=r;++i) {
            bkt[arr[i]=arr[find(i)]]++;
            asi[get2(arr[i])]++;
            // printf("bkt[%d] = %d, asi[%d] = %d\n",arr[find(i)],bkt[arr[find(i)]],get2(arr[find(i)]),asi[get2(arr[find(i)])]);
        }
        int sum=0;
        int blk;
        for (blk=0;blk<bk2;++blk) {
            if (sum+asi[blk]<k) {
                sum+=asi[blk];
            } else {
                break;
            }
        }
        for (int i=getl2(blk);i<=getr2(blk);++i) {
            if (sum+bkt[i]<k) {
                sum+=bkt[i];
            } else {
                return i;
            }
        }
    } else {
        memset(asi,0,sizeof(asi));
        memset(bkt,0,sizeof(bkt));
        // cout<<l<<" "<<get(l)<<" "<<getr(get(l))<<endl;
        for (int i=l;i<=getr(get(l));++i) {
            bkt[arr[i]=arr[find(i)]]++;
            asi[get2(arr[i])]++;
            // printf("L: bkt[%d] = %d, asi[%d] = %d\n",arr[find(i)],bkt[arr[find(i)]],get2(arr[find(i)]),asi[get2(arr[find(i)])]);
        }
        for (int i=getl(get(r));i<=r;++i) {
            bkt[arr[i]=arr[find(i)]]++;
            asi[get2(arr[i])]++;
            // printf("R: bkt[%d] = %d, asi[%d] = %d\n",arr[find(i)],bkt[arr[find(i)]],get2(arr[find(i)]),asi[get2(arr[find(i)])]);
        }
        int sum=0;
        int blk;
        for (blk=0;blk<bk2;++blk) {
            if (sum+seg[get(r)-1][blk]-seg[get(l)][blk]+asi[blk]<k) {
                sum+=seg[get(r)-1][blk]-seg[get(l)][blk]+asi[blk];
            } else {
                break;
            }
        }
        for (int i=getl2(blk);i<=getr2(blk);++i) {
            if (sum+pre[get(r)-1][i]-pre[get(l)][i]+bkt[i]<k) {
                sum+=pre[get(r)-1][i]-pre[get(l)][i]+bkt[i];
            } else {
                return i;
            }
        }
    }
    // assert(false);
    return -114514;
}

int main() {
    scanf("%d %d",&n,&m);
    len=415; bk=n/len; if (n%len) bk++;
    len2=305; bk2=100000/len2; if (100000%len2) bk2++;
    for (int i=1;i<=n;++i) {
        scanf("%d",&arr[i]);
    }
    init();
    while (m--) {
        int op,l,r;
        scanf("%d %d %d",&op,&l,&r);
        if (op==1) {
            int x,y;
            scanf("%d %d",&x,&y);
            modify(l,r,x,y);
        } else {
            int k;
            scanf("%d",&k);
            int ans=query(l,r,k);
            printf("%d\n",ans);
        }
    }
    return 0;
}

/*
cnt[i][j] 第 i 块 j 出现次数
pre[i][j] 前 i 块 j 出现次数
seg[i][j] 前 i 块值域第 j 块出现次数
*/

参考了这篇题解：https://www.luogu.com.cn/article/jahbeydc，然后不知道为什么全部 RE 了，好想是 Floating-point exception，不知道哪里出现除 0 的错误，大佬帮忙看看吧（（（蒟蒻刚学分块 0.1ms）））