1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
// Witold Milewski
// PA 2025
#include <bits/stdc++.h>
#define i128 __int128_t
using namespace std;
#define gc getchar_unlocked
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define FORB(i, b, a) for(int i=b; i>=a; --i)
#define sz(A) (int)(A.size())
#define eb emplace_back
#define pb push_back
#define pi pair<int, int>
#define f first
#define s second
#define rs resize
#define V vector

int n, m, k, q;

V<int> p, l, d, g, pp, ll, dd, gg;
map<pi, int> klocek_id;
set<int> klocki_id;
V<pi> punkty;
int id=0, odp=0;

void rozw() {
  odp=0;
  V<int> kol;
  V<bool> del(id+1, 0);
  del[0]=1;
  for(auto &kloc : klocki_id) if(((p[kloc]==0&&l[kloc]==0) || (d[kloc]==0&&g[kloc]==0))) kol.eb(kloc), del[kloc]=1, ++odp;
  while(!kol.empty()) {
    int idx = kol.back(); kol.pop_back();
    auto [x, y] = punkty[idx];
    if((p[idx]!=0 && del[p[idx]]==0) && del[pp[idx]]==1) kol.eb(p[idx]), del[p[idx]]=1, ++odp;
    if((l[idx]!=0 && del[l[idx]]==0) && del[ll[idx]]==1) kol.eb(l[idx]), del[l[idx]]=1, ++odp;
    if((g[idx]!=0 && del[g[idx]]==0) && del[gg[idx]]==1) kol.eb(g[idx]), del[g[idx]]=1, ++odp;
    if((d[idx]!=0 && del[d[idx]]==0) && del[dd[idx]]==1) kol.eb(d[idx]), del[d[idx]]=1, ++odp;
  }
}

void wcz(int &a) {
  a=0;
  char c=gc();
  while(c<'0'||c>'9') c=gc();
  while(c>='0' && c<='9') a=10*a+c-'0', c=gc();
}

void update(int idx) {
  auto [x, y] = punkty[idx];
  p[klocek_id[{x-1,y}]]=idx;
  l[klocek_id[{x+1,y}]]=idx;
  d[klocek_id[{x,y+1}]]=idx;
  g[klocek_id[{x,y-1}]]=idx;
  pp[klocek_id[{x-2,y}]]=idx;
  ll[klocek_id[{x+2,y}]]=idx;
  dd[klocek_id[{x,y+2}]]=idx;
  gg[klocek_id[{x,y-2}]]=idx;

  p[idx]=klocek_id[{x+1,y}];
  l[idx]=klocek_id[{x-1,y}];
  d[idx]=klocek_id[{x,y-1}];
  g[idx]=klocek_id[{x,y+1}];
  pp[idx]=klocek_id[{x+2,y}];
  ll[idx]=klocek_id[{x-2,y}];
  dd[idx]=klocek_id[{x,y-2}];
  gg[idx]=klocek_id[{x,y+2}];
}

void remove(int idx) {
  auto [x,y] = punkty[idx];
  p[klocek_id[{x-1,y}]]=0;
  l[klocek_id[{x+1,y}]]=0;
  d[klocek_id[{x,y+1}]]=0;
  g[klocek_id[{x,y-1}]]=0;
  pp[klocek_id[{x-2,y}]]=0;
  ll[klocek_id[{x+2,y}]]=0;
  dd[klocek_id[{x,y+2}]]=0;
  gg[klocek_id[{x,y-2}]]=0;
}

signed main() {
  wcz(n); wcz(m); wcz(k); wcz(q);
  punkty.rs(k+q+1);
  p.rs(k+q+1);
  l.rs(k+q+1);
  g.rs(k+q+1);
  d.rs(k+q+1);
  pp.rs(k+q+1);
  ll.rs(k+q+1);
  dd.rs(k+q+1);
  gg.rs(k+q+1);


  int x, y;
  FOR(i, 1, k) {
    wcz(x); wcz(y);
    ++id;
    klocek_id[{x,y}]=id;
    klocki_id.insert(id);
    punkty[id]={x,y};
    update(id);    
  }
  rozw();
  printf("%d\n", odp);

  FOR(i, 1, q) {
    wcz(x); wcz(y);
    if(klocek_id[{x,y}]==0) {
      ++id;
      klocek_id[{x,y}]=id;
      punkty[id]={x,y};
      klocki_id.insert(id);
      update(id);
    } else {
      klocki_id.erase(klocek_id[{x,y}]);
      remove(klocek_id[{x,y}]);
      klocek_id[{x,y}]=0;
    }
    rozw();
    printf("%d\n", odp);
  }
}