#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include #include #include #include #include #include #include #include #include using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<(i64)(n); i++) #define repr(i,n) for(i64 i=(i64)(n)-1; i>=0; i--) const i64 INF = 1001001001001001001; const char* yn(bool x){ return x ? "Yes" : "No"; } template void chmin(A& l, const A& r){ if(r < l) l = r; } template void chmax(A& l, const A& r){ if(l < r) l = r; } template using nega_queue = std::priority_queue,std::greater>; using Modint = atcoder::static_modint<998244353>; //#include "nachia/vec.hpp" #include using namespace std; void testcase(){ i64 H, W, N; cin >> H >> W >> N; i64 D; cin >> D; vector> P(N); for(auto& [x,y] : P){ cin >> x >> y; x--; y--; } sort(P.begin(), P.end()); auto dist = [&](i64 a, i64 b) -> i64 { return abs(P[a].first - P[b].first) + abs(P[a].second - P[b].second); }; vector iso(N); atcoder::dsu dsu(N); i64 a = 0; { vector lasti(W+D+5, -1); rep(i,N){ auto [x,y] = P[i]; for(i64 yy=max(y-D,0); yy= 0 && dist(lasti[yy], i) <= D) dsu.merge(lasti[yy], i); } lasti[y] = i; } rep(i,N) if(dsu.leader(i) == i && dsu.size(i) != 1) a++; rep(i,N) if(dsu.size(i) == 1) iso[i] = 1; } i64 lb = a, ub = a; bool down_lb = false; { vector lasti(W+D*2+1, -1); rep(i,N) if(!iso[i]){ auto [x,y] = P[i]; for(i64 yy=max(y-D*2,0); yy= 0 && dist(lasti[yy], i) <= D*2 && !dsu.same(lasti[yy], i)){ down_lb = true; } } lasti[y] = i; } rep(i,N) if(dsu.leader(i) == i && dsu.size(i) != 1) a++; rep(i,N) if(dsu.size(i) == 1) iso[i] = 1; } bool up_ub = false; rep(ttt,4){ vector lasti(W+D+1, -1); vector> byx(H); rep(i,N) byx[P[i].first].push_back(i); rep(x,H){ for(int i : byx[x]){ auto [x,y] = P[i]; for(i64 yy=max(y-D,0); yy= 0 && dist(lasti[yy], i) <= D + 1) ok = false; if(x != 0 && ok) up_ub = true; } } for(int i : byx[x]) if(!iso[i]){ auto [x,y] = P[i]; lasti[y] = i; } } swap(H, W); for(auto& [x,y] : P){ swap(x,y); y = W - 1 - y; } } if(down_lb) lb--; if(up_ub) ub++; cout << lb << " " << ub << "\n"; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef NACHIA int T; cin >> T; for(int t=0; t