#include <bits/stdc++.h>
using namespace std;
const int NN=5e5+10;

int n;
int b[NN<<1],btot;
int id[NN],tot;

struct DSU{
    int fa[NN];

    void init() {
        for(int i=1;i<=n;i++) fa[i]=i;
    }

    int get(int x) {
        if(fa[x]==x) return x;
        return fa[x]=get(fa[x]);
    }

    void mg(int u,int v) {
        u=get(u),v=get(v);
        if(u==v) return ;
        fa[u]=v;
    }
}dsu;

void calc(vector<pair<pair<pair<int,int>,pair<int,int> >,int> > arr1,vector<pair<pair<pair<int,int>,pair<int,int> >,int> > arr2) {
    vector<pair<pair<int,int>,int> > arr;
    pair<pair<int,int>,int> lst={{-2e9,-2e9},0};
    for(auto i:arr1) {
        int l=i.first.first.first,r=i.first.first.second,id=i.second;
        if(l<=lst.first.second) dsu.mg(lst.second,id),lst.first.second=max(lst.first.second,r);
        else {
            if(lst.second) arr.push_back(lst);
            lst={{l,r},id};
        }
    }
    if(lst.second) arr.push_back(lst);
    vector<pair<pair<int,int>,int> > stk;
    reverse(arr.begin(),arr.end());
    reverse(arr2.begin(),arr2.end());
    int now=0;
    for(auto i:arr2) {
        int l=i.first.first.first,r=i.first.first.second,id=i.second;
        while(now<arr.size() && arr[now].first.second>=l) stk.push_back(arr[now++]);
        if(!stk.size() || stk.back().first.first>r) continue;
        pair<pair<int,int>,int> lst=stk.back();
        lst.first.second=max(lst.first.second,r);
        dsu.mg(id,lst.second);
        stk.pop_back();
        while(!stk.empty() && stk.back().first.first<=lst.first.second) {
            dsu.mg(lst.second,stk.back().second);
            lst.first.second=max(lst.first.second,stk.back().first.second);
            stk.pop_back();
        }
        stk.push_back(lst);
    }
}

void solve(int L,int R,vector<pair<pair<pair<int,int>,pair<int,int> >,int> > arr) {
    if(arr.size()<=1) return ;
    int mid=L+R>>1;
    vector<pair<pair<pair<int,int>,pair<int,int> >,int> > arrl,arrr,now;
    for(auto i:arr) {
        int l=i.first.second.first,r=i.first.second.second;
        if(L>=l && R<=r) now.push_back(i);
        else {
            if(mid>=l) arrl.push_back(i);
            if(mid+1<=r) arrr.push_back(i);
        }
    }
    calc(now,arr);
    if(L==R) return ;
    solve(L,mid,arrl);
    solve(mid+1,R,arrr);
}

vector<int> find_union(int N,vector<int> A,vector<int> B,vector<int> C,vector<int> D) {
    n=N;
    for(int i:A) b[++btot]=i;
    for(int i:C) b[++btot]=i;
    sort(b+1,b+1+btot),btot=unique(b+1,b+1+btot)-b-1;
    for(int i=0;i<n;i++) A[i]=lower_bound(b+1,b+1+btot,A[i])-b,C[i]=lower_bound(b+1,b+1+btot,C[i])-b;
    dsu.init();
    vector<pair<pair<pair<int,int>,pair<int,int> >,int> > arr;
    for(int i=0;i<n;i++) {
        arr.push_back({{{B[i],D[i]},{A[i],C[i]}},i+1});
    }
    sort(arr.begin(),arr.end());
    solve(1,btot,arr);
    vector<int> ans;
    tot=0;
    for(int i=1;i<=n;i++) if(!id[dsu.get(i)]) id[dsu.get(i)]=++tot;
    for(int i=1;i<=n;i++) ans.push_back(id[dsu.get(i)]-1);
    return ans;
}