#include using namespace std; #define rep(i, n) for(long long i=0;i<(long long)(n);i++) #define REP(i,k,n) for(long long i=k;i<(long long)(n);i++) #define pb emplace_back #define lb(v,k) (lower_bound(all(v),(k))-v.begin()) #define ub(v,k) (upper_bound(all(v),(k))-v.begin()) #define fi first #define se second #define pi M_PI #define PQ(T) priority_queue #define SPQ(T) priority_queue,greater> #define dame(a) {out(a);return 0;} #define decimal cout< P; typedef tuple PP; typedef tuple PPP; using vi=vector; using vvi=vector; using vvvi=vector; using vvvvi=vector; using vpp=vector; using vvpp=vector; using vvvpp=vector; using vvvvpp=vector; using vp=vector

; using vvp=vector; using vb=vector; using vvb=vector; const ll inf=1001001001001001001; const ll INF=1001001001; const ll mod=1000000007; const double eps=1e-10; template bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;} template bool chmax(T&a,T b){if(a void out(T a){cout< void outp(T a){cout<<'('< void outvp(T v){rep(i,v.size())cout<<'('< void outvvp(T v){rep(i,v.size())outvp(v[i]);} template void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout< void outvv(T v){rep(i,v.size())outv(v[i]);} template bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);} template void yesno(T b){if(b)out("yes");else out("no");} template void YesNo(T b){if(b)out("Yes");else out("No");} template void YESNO(T b){if(b)out("YES");else out("NO");} template void outset(T s){auto itr=s.begin();while(itr!=s.end()){if(itr!=s.begin())cout<<' ';cout<<*itr;itr++;}cout<<'\n';} void outs(ll a,ll b){if(a>=inf-100)out(b);else out(a);} ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);} ll modpow(ll a,ll b,ll m){ll res=1;a%=m;while(b){if(b&1)res=res*a%m;a=a*a%m;b>>=1;}return res;} class BIT{ vi bit;ll n; ll sum(ll i){ ll res=0; for(;i;i-=i&-i)res+=bit[i]; return res; } public: BIT(ll n_):n(n_){bit=vi(n+1);} void add(ll i,ll x){ for(i++;i<=n;i+=i&-i)bit[i]+=x; } ll get(ll a,ll b){ if(b<=a)return 0ll; return sum(b)-sum(a); } ll solve(ll x){ //sum([0,r])>=x となる最小のr if(x<=0)return -1; ll l=0,len=1;while(len>=1)if(l+len st; public: UF(ll n){ data=vi(n,1); } bool merge(ll x,ll y,bool undo=false){ // outp(P(x,y)); x=root(x);y=root(y); if(data[x]>data[y])swap(x,y); if(undo){st.emplace(y,data[y]);st.emplace(x,data[x]);} if(x==y)return false; data[y]+=data[x];data[x]=-y; return true; } ll root(ll i){if(data[i]>0)return i;return root(-data[i]);} ll getsize(ll i){return data[root(i)];} bool same(ll a,ll b){return root(a)==root(b);} void undo(){rep(i,2){data[st.top().fi]=st.top().se;st.pop();}} }; int main() { ll h=INF,w=INF,A,B;cin>>A>>B; ll n=A+B; vvi tate,yoko; tate.pb(vi{0,0,w}); tate.pb(vi{h,0,w}); yoko.pb(vi{0,0,h}); yoko.pb(vi{w,0,h}); vi sx,sy; sx.pb(0);sx.pb(h);sy.pb(0);sy.pb(w); rep(i,n){ ll a,b,c,d; if(i>b>>a>>c;d=b; } else{ cin>>a>>b>>d;c=a; } sx.pb(a);sx.pb(c);sy.pb(b);sy.pb(d); if(a==c)tate.pb(vi{a,b,d}); else yoko.pb(vi{b,a,c}); } dupli(sx);dupli(sy); sort(all(tate));sort(all(yoko)); vvi ad(sx.size()),er(sx.size()); vvi ad2(sy.size()),er2(sy.size()); rep(i,tate.size()){ tate[i][0]=lb(sx,tate[i][0]); tate[i][1]=lb(sy,tate[i][1]); tate[i][2]=lb(sy,tate[i][2]); ad2[tate[i][1]].pb(i); er2[tate[i][2]].pb(i); } rep(i,yoko.size()){ yoko[i][0]=lb(sy,yoko[i][0]); yoko[i][1]=lb(sx,yoko[i][1]); yoko[i][2]=lb(sx,yoko[i][2]); ad[yoko[i][1]].pb(i); er[yoko[i][2]].pb(i); } // outv(sx);outv(sy); ll cnt_ver=0,cnt_edge=0,cnt_ren=0; ll idx=0; BIT bit(sy.size()); rep(i,sx.size()){ set S; for(ll j:er[i]){ S.insert(yoko[j][0]); bit.add(yoko[j][0],-1); } while(idx S; ll idx=0; rep(i,sx.size()){ for(ll j:ad[i]){ auto itr=S.lower_bound(j); if(itr!=S.begin()){ itr--; ll prev=*itr; ll tmp=bit.get(0,prev+1); if(tmp){ itr++; uf.merge(prev,*itr); itr--; bit.add(prev,-tmp); bit.add(prev+1,tmp); } } S.insert(j); ll tmp=bit.get(0,j+1); bit.add(j,-tmp); bit.add(j+1,tmp); } while(idx