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
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;

vector <int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

map <pair <int, int>, bool> b, unrem;

bool check(int x, int y) {
	if((unrem.contains({x - 1, y}) && unrem.contains({x + 1, y})) || (unrem.contains({x, y - 1}) && unrem.contains({x, y + 1}))) return 1;
	return 0;
}

bool w_kwadracie(int x0, int y0) {
	for(int x = x0 - 1; x <= x0; ++x) {
		for(int y = y0 - 1; y <= y0; ++y) {
			if(b.contains({x, y}) && b.contains({x + 1, y}) && b.contains({x, y + 1}) && b.contains({x + 1, y + 1})) {
				return 1;
			}
		}
	}
	return 0;
}

int main() {
	int n, m, k, Q; scanf("%d%d%d%d", &n, &m, &k, &Q);

	for(int i = 0; i < k; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		b[{x, y}] = 1;
	}

	queue <pair <int, int> > q;
	for(auto &pm : b) {
		auto p = pm.first;
		int x = p.first, y = p.second;
		if(b.contains({x + 1, y}) && b.contains({x, y + 1}) && b.contains({x + 1, y + 1})) {
			if(!unrem.contains({x, y})) q.push({x, y});
			if(!unrem.contains({x + 1, y})) q.push({x + 1, y});
			if(!unrem.contains({x, y + 1})) q.push({x, y + 1});
			if(!unrem.contains({x + 1, y + 1})) q.push({x + 1, y + 1});
			unrem[{x, y}] = 1;
			unrem[{x + 1, y}] = 1;
			unrem[{x, y + 1}] = 1;
			unrem[{x + 1, y + 1}] = 1;
		}
	}

	int ans = 0;
	while(!q.empty()) {
		auto p = q.front();
		q.pop();

		++ans;

		int x = p.first, y = p.second;

		for(int i = 0; i < 4; ++i) {
			int x1 = x + dx[i], y1 = y + dy[i];
			if(x1 < 1 || x1 > n || y1 < 1 || y1 > m || !b.contains({x1, y1})) continue;

			if(!unrem.contains({x1, y1}) && check(x1, y1)) {
				unrem[{x1, y1}] = 1;
				q.push({x1, y1});
			}
		}
	}

	printf("%d\n", k - ans);

	for(int qq = 0; qq < Q; ++qq) {
		int x0, y0; scanf("%d%d", &x0, &y0);

		if(b.contains({x0, y0})) {
			--k;
			b.erase({x0, y0});
			if(!unrem.contains({x0, y0})) {
				continue;
			}
			else {
				q.push({x0, y0});
				while(!q.empty()) {
					auto p = q.front();
					q.pop();

					--ans;

					int x = p.first, y = p.second;

					for(int i = 0; i < 4; ++i) {
						int x1 = x + dx[i], y1 = y + dy[i];
						if(x1 < 1 || x1 > n || y1 < 1 || y1 > m || !b.contains({x1, y1})) continue;

						if(unrem.contains({x1, y1}) && !check(x1, y1)) {
							unrem.erase({x1, y1});
							q.push({x1, y1});
						}
					}
				}
			}
		}
		else {
			++k;
			b[{x0, y0}] = 1;
			if(check(x0, y0) || w_kwadracie(x0, y0)) {
				unrem[{x0, y0}] = 1;
				q.push({x0, y0});
				while(!q.empty()) {
					auto p = q.front();
					q.pop();

					++ans;

					int x = p.first, y = p.second;

					for(int i = 0; i < 4; ++i) {
						int x1 = x + dx[i], y1 = y + dy[i];
						if(x1 < 1 || x1 > n || y1 < 1 || y1 > m || !b.contains({x1, y1})) continue;

						if(!unrem.contains({x1, y1}) && check(x1, y1)) {
							unrem[{x1, y1}] = 1;
							q.push({x1, y1});
						}
					}
				}
			}
		}

		printf("%d\n", k - ans);
	}

	return 0;
}