#include using namespace std; typedef signed long long ll; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) //------------------------------------------------------- template class SegTree_max { public: vector val; static V const def=0; V comp(V l,V r){ return max(l,r);}; SegTree_max(){val=vector(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; template class SegTree_min { public: vector val; static V const def=1<<30; V comp(V l,V r){ return min(l,r);}; SegTree_min(){val=vector(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_min SR,SD; SegTree_max SL,ST; int H,W,N,OH,OW; int X[101010],Y[101010],L[101010]; vector Xs,Ys; int DL[101010]; int DR[101010]; int DT[101010]; int DD[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W>>N; Xs.push_back(0); Xs.push_back(W+1); Ys.push_back(0); Ys.push_back(H+1); FOR(i,N) { cin>>X[i]>>Y[i]>>L[i]; if(X[i]==0 || X[i]==W+1) Ys.push_back(Y[i]); else Xs.push_back(X[i]); } sort(ALL(Xs)); sort(ALL(Ys)); Xs.erase(unique(ALL(Xs)),Xs.end()); Ys.erase(unique(ALL(Ys)),Ys.end()); OW=W; OH=H; W=Xs.size(); H=Ys.size(); FOR(i,H) SR.update(i,DR[i]=OW+1); FOR(i,W) SD.update(i,DD[i]=OH+1); FOR(i,N) { if(X[i]==0 || X[i]==OW+1) { y=lower_bound(ALL(Ys),Y[i])-Ys.begin(); if(X[i]==0) { int xt=W-1,xd=W-1; for(j=20;j>=0;j--) { if(ST.getval(0,xt-(1<=Y[i]) xt-=1<=0;j--) { if(xt+(1<=Y[i]) xt+=1<=DR[y]) { DR[y]=OW+1; if(Xs[xt]>Xs[xd]&&Xs[xt]>DL[y]) ST.update(xt,DT[xt]=0); if(Xs[xd]>Xs[xt]&&Xs[xd]>DL[y]) SD.update(xd,DD[xd]=OH+1); if(DL[y]>Xs[xt]&&DL[y]>Xs[xd]) SL.update(y,DL[y]=0); } SR.update(y,DR[y]); } } else { x=lower_bound(ALL(Xs),X[i])-Xs.begin(); if(Y[i]==0) { int yl=H-1,yr=H-1; for(j=20;j>=0;j--) { if(SL.getval(0,yl-(1<=X[i]) yl-=1<=0;j--) { if(yl+(1<=X[i]) yl+=1<=DD[x]) { DD[x]=OH+1; if(Ys[yl]>Ys[yr]&&Ys[yl]>DT[x]) SL.update(yl,DL[yl]=0); if(Ys[yr]>Ys[yl]&&Ys[yr]>DT[x]) SR.update(yr,DR[yr]=OW+1); if(DT[x]>Ys[yl]&&DT[x]>Ys[yr]) ST.update(x,DT[x]=0); } SD.update(x,DD[x]); } } /* for(x=1;x<=W-2;x++) cout<<"#"<