#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define eb emplace_back
#define vi vector<int>
#define ll long long
using namespace std;
const int N=1000007;
int n,L[N],R[N],U[N],G[N],p[N],t[N<<2],f[N],pd,o,bh[N];
vi A,B,C,D,X,Y,ans;
void upd(int x,int y){while(x<=n+n)f[x]+=y,x+=x&-x;}
int qry(int x){int s=0;while(x)s+=f[x],x-=x&-x;return s;}
int find(int x){return x==p[x]?x:p[x]=find(p[x]);}
void mer(int l,int r,int o,int x,int y,int c)
{
	if(t[o]==-1) return;
	int mid=l+r>>1;
	if(x<=l&&r<=y)
	{
		if(t[o]) p[find(t[o])]=find(c);
		else mer(l,mid,o+o,x,y,c),mer(mid+1,r,o+o+1,x,y,c),t[o]=c;
		return;
	}
	if(x<=mid) mer(l,mid,o+o,x,y,c);
	if(y>mid) mer(mid+1,r,o+o+1,x,y,c);
}
void ins(int l,int r,int o,int x,int c)
{
	if(l==r){t[o]=c;return;}
	int mid=l+r>>1;
	if(x<=mid) ins(l,mid,o+o,x,c);
	else ins(mid+1,r,o+o+1,x,c);
	t[o]=t[o+o]+t[o+o+1]==-2?-1:0;
}
void fnd(int l,int r,int o,int x,int y)
{
	if(pd) return;
	if(t[o]==-1) return;
	if(l==r){p[find(t[o])]=find(y);pd=1;return;}
	int mid=l+r>>1;
	if(x>mid) fnd(mid+1,r,o+o+1,x,y);
	fnd(l,mid,o+o,x,y);
}
vi find_union(int _n,vi A,vi B,vi C,vi D)
{
	X.clear();Y.clear();o=0;ans.clear();
	fo(i,1,n) bh[i]=0;
	n=_n;
	fu(i,0,n) X.eb(A[i]*2),X.eb(C[i]*2+1),Y.eb(B[i]*2),Y.eb(D[i]*2+1);
	sort(X.begin(),X.end());
	sort(Y.begin(),Y.end());
	fo(i,1,n)
	{
		int x=lower_bound(X.begin(),X.end(),A[i-1]*2)-X.begin();X[x]--;
		int u=lower_bound(X.begin(),X.end(),C[i-1]*2+1)-X.begin();X[u]--;
		int y=lower_bound(Y.begin(),Y.end(),B[i-1]*2)-Y.begin();Y[y]--;
		int v=lower_bound(Y.begin(),Y.end(),D[i-1]*2+1)-Y.begin();Y[v]--;
		x++;y++;u++;v++;
		L[x]=L[u]=y;R[x]=R[u]=v;U[x]=U[u]=i;G[x]=1;G[u]=-1;p[i]=i;
	}
	fu(i,0,N<<2) t[i]=-1;
	fo(i,1,n+n)
	{
		upd(L[i],G[i]);upd(R[i],-G[i]);
		if(qry(L[i]-1)>0) pd=0,fnd(1,n+n,1,L[i]-1,U[i]);
		ins(1,n+n,1,L[i],G[i]>0?U[i]:-1);ins(1,n+n,1,R[i],G[i]>0?U[i]:-1);
		mer(1,n+n,1,L[i],R[i],U[i]);
	}
	fo(i,1,n) if(i==p[i]) bh[i]=o++;
	fo(i,1,n) ans.eb(bh[find(i)]);
	return ans;
}