wtcl /kk

（代码是根据以前写的区间 $x$ 改 $y$ 和第 $k$ 小值改的）：

#include<bits/stdc++.h>
//#define int register int
using namespace std;
/*
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
    	if(ch=='-')f=-1;
    	ch=getchar();
	}
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
*/
/*
static char buf[100000],*pa=buf,*pd=buf;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read()
{
    register int x(0);register char c(gc);
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;
    return x;
}
*/

inline void write(int x){
    if(x<0) x=~x+1,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}

inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
   
   
    char ch=nc();x=0;
    while (!(ch>='0'&&ch<='9')) ch=nc();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=nc();
}
const int N=100005;
const int M=170;
const int S=320;
int size=600,sizeval=317,mval=1e5;
int n,m,block,a[N];
int top=0,sta[N];
int L[M],R[M];
int bel[N];
int s1[S],s2[N]; 
int cnt[M][N];
int sumc[M][N],sums[M][S];

int fa[N],rt[M][N];
int find(int x){
	if(fa[x]==x) return fa[x];
	fa[x]=find(fa[x]);
	return fa[x];
}
void Build(int b){
	for(register int i=L[b];i<=R[b];i++){
		if(!rt[b][a[i]]) rt[b][a[i]]=i;
		else fa[i]=rt[b][a[i]];
		cnt[b][a[i]]++;
	}
}
void ReBuild(int b,int l,int r,int x,int y){
	int tmp=0;
	top=0;
	rt[b][x]=rt[b][y]=0;
	for(register int i=L[b];i<=R[b];i++){
		a[i]=a[find(i)];
		if(a[i]==x||a[i]==y) sta[++top]=i;
	}
	for(register int i=l;i<=r;i++){
		if(a[i]==x) a[i]=y,tmp++;
	}
	cnt[b][x]-=tmp,cnt[b][y]+=tmp;
	for(register int i=1;i<=top;i++) fa[sta[i]]=sta[i];
	for(register int i=1;i<=top;i++){
		if(!rt[b][a[sta[i]]]) rt[b][a[sta[i]]]=sta[i];
		else fa[sta[i]]=rt[b][a[sta[i]]]; 
	}
	for(register int i=b;i<=block;i++){
		sumc[i][x]-=tmp,sumc[i][y]+=tmp;
		if(bel[x]!=bel[y]) sums[i][bel[x]]-=tmp,sums[i][bel[y]]+=tmp;
	}
}
void update(int l,int r,int x,int y){
	int lb=(l-1)/size+1;
	int rb=(r-1)/size+1;
	if(lb==rb) ReBuild(lb,l,r,x,y);
	else{
		ReBuild(lb,l,R[lb],x,y);
		ReBuild(rb,L[rb],r,x,y);
		int tmp=0,tmps=0;
		for(register int i=lb+1;i<=rb-1;i++){
			if(rt[i][x]){
				if(!rt[i][y]) rt[i][y]=rt[i][x],a[rt[i][x]]=y;
				else fa[rt[i][x]]=rt[i][y];
				rt[i][x]=0;
				tmp=cnt[i][x];
				tmps+=tmp;
				cnt[i][y]+=tmp,cnt[i][x]=0;
			}
			sumc[i][x]-=tmps,sumc[i][y]+=tmps;
			if(bel[x]!=bel[y]) sums[i][bel[x]]-=tmps,sums[i][bel[y]]+=tmps;
		}
		for(register int i=rb;i<=block;i++){
			sumc[i][x]-=tmps,sumc[i][y]+=tmps;
			if(bel[x]!=bel[y]) sums[i][bel[x]]-=tmps,sums[i][bel[y]]+=tmps;
		}
	}
}
void query(int l,int r,int k){
	int lb=(l-1)/size+1;
	int rb=(r-1)/size+1;
	if(lb==rb){
		for(int i=l;i<=r;i++){
			a[i]=a[find(i)];
			s1[bel[a[i]]]++;
			s2[a[i]]++;
		}
		int vl,vr,sum=0;
		for(register int i=1;i<=sizeval;i++){
			sum+=s1[i];
			if(sum>=k){
				sum-=s1[i];
				vl=(i-1)*sizeval+1,vr=i*sizeval;
				break;
			}
		}
		for(register int i=vl;i<=vr;i++){
			sum+=s2[i];
			if(sum>=k){
				write(i);
				putchar(' ');
				break;
			}
		}
		for(register int i=l;i<=r;i++) s2[a[i]]--,s1[bel[a[i]]]--;
	}
	else{
		for(register int i=l;i<=R[lb];i++){
			a[i]=a[find(i)];
			s1[bel[a[i]]]++;
			s2[a[i]]++;
		}
		for(register int i=L[rb];i<=r;i++){
			a[i]=a[find(i)];
			s1[bel[a[i]]]++;
			s2[a[i]]++;
		}
		int vl,vr,sum=0;
		for(register int i=1;i<=sizeval;i++){
			sum+=s1[i]+sums[rb-1][i]-sums[lb][i];
			if(sum>=k){
				sum-=s1[i]+sums[rb-1][i]-sums[lb][i];
				vl=(i-1)*sizeval+1,vr=i*sizeval;
				break;
			}
		}
		for(register int i=vl;i<=vr;i++){
			sum+=s2[i]+sumc[rb-1][i]-sumc[lb][i];
			if(sum>=k){
				write(i);
				putchar(' ');
				break;
			} 
		}
		for(register int i=l;i<=R[lb];i++){
			s1[bel[a[i]]]--;
			s2[a[i]]--;
		}
		for(register int i=L[rb];i<=r;i++){
			s1[bel[a[i]]]--;
			s2[a[i]]--;
		}
	}
}
signed main(){
	read(n);
	for(register int i=1;i<=n;i++){
		read(a[i]);
		fa[i]=i;
	}
	block=(n-1)/size+1;
	for(register int i=1;i<=mval;i++) bel[i]=(i-1)/sizeval+1;
	for(register int i=1;i<=block;i++){
		L[i]=(i-1)*size+1;
		R[i]=min(i*size,n);
		Build(i);
		for(register int j=1;j<=sizeval;j++) sums[i][j]=sums[i-1][j];
		for(register int j=1;j<=mval;j++) sumc[i][j]=sumc[i-1][j]+cnt[i][j];
		for(register int j=L[i];j<=R[i];j++) sums[i][bel[a[j]]]++;
	}
	read(m);
	while(m--){
		int x,y,l,r;
		read(l),read(r),read(x),read(y);
		if(x==y) continue;
		update(l,r,x,y);
	}
	for(int i=1;i<=n;i++) query(i,i,1);
	return 0;
}