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
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> par;
vector<par> wie[200009], kol[200009];
int n, m, k, q, nex, col[150009];
queue<int> qu;
par poz[150009], pio[150009];

void check(int a, int b)
{
    int wyn = 0, c, d, x, y;
    par p;
    bool istaken = 0;
    while(!qu.empty()) qu.pop();
    for(int i=1; i<=k+q; i++) col[i] = 0;
    for(int i=1; i<=n; i++) {
        if(i == a) {
            for(int j=0; j<wie[i].size(); j++) {
                if(wie[i][j].first == b) {
                    swap(wie[i][j], wie[i][wie[i].size()-1]);
                    wie[i].pop_back();
                    istaken = 1;
                    break;
                }
            }
            if(!istaken) wie[i].push_back(par(b, nex));
            sort(wie[i].begin(), wie[i].end());
        }
        c = -3;
        for(int j=0; j<wie[i].size()-1; j++) {
			poz[wie[i][j].second] = par(i, j);
			d = wie[i][j+1].first;
			if(wie[i][j].first > c + 1 && wie[i][j].first < d - 1) qu.push(wie[i][j].second);
			c = wie[i][j].first;
		}
    }
    
    for(int j=1; j<=m; j++) {
        if(j == b) {
            for(int i=0; i<kol[j].size(); i++) {
                if(kol[j][i].first == a) {
                    swap(kol[j][i], kol[j][kol[j].size()-1]);
                    kol[j].pop_back();
                    istaken = 1;
                    break;
                }
            }
            if(!istaken) {
				kol[j].push_back(par(a, nex));
				nex++;
			}
            sort(kol[j].begin(), kol[j].end());
        }
        c = -3;
        for(int i=0; i<kol[j].size()-1; i++) {
			pio[kol[j][i].second] = par(j, i);
			d = kol[j][i+1].first;
			if(kol[j][i].first > c + 1 && kol[j][i].first < d - 1) qu.push(kol[j][i].second);
			c = kol[j][i].first;
		}
    }


	while(!qu.empty()) {
		c = qu.front();
		qu.pop();
		if(col[c] == 1) continue;
		col[c] = 1;
		wyn++;
		p = poz[c];
		if(p.second > 0 && wie[p.first][p.second].first == wie[p.first][p.second-1].first + 1) {
			if(p.second == 1 || col[wie[p.first][p.second-2].second] == 1 || wie[p.first][p.second-2].first + 1 < wie[p.first][p.second-1].first) {
				qu.push(wie[p.first][p.second-1].second);
			}
		}
		if(p.second < wie[p.first].size() - 2 && wie[p.first][p.second].first == wie[p.first][p.second+1].first - 1) {
			if(col[wie[p.first][p.second+2].second] == 1 || wie[p.first][p.second+2].first - 1 > wie[p.first][p.second+1].first) {
				qu.push(wie[p.first][p.second+1].second);
			}
		}
		
		p = pio[c];
		if(p.second > 0 && kol[p.first][p.second].first == kol[p.first][p.second-1].first + 1) {
			if(p.second == 1 || col[kol[p.first][p.second-2].second] == 1 || kol[p.first][p.second-2].first + 1 < kol[p.first][p.second-1].first) {
				qu.push(kol[p.first][p.second-1].second);
			}
		}
		if(p.second < kol[p.first].size() - 2 && kol[p.first][p.second].first == kol[p.first][p.second+1].first - 1) {
			if(col[kol[p.first][p.second+2].second] == 1 || kol[p.first][p.second+2].first - 1 > kol[p.first][p.second+1].first) {
				qu.push(kol[p.first][p.second+1].second);
			}
		}
	}
    cout<<wyn<<'\n';
    return;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int a, b;
    cin>>n>>m>>k>>q;
    for(int i=1; i<=k; i++) {
        cin>>a>>b;
        wie[a].push_back(par(b, i));
        kol[b].push_back(par(a, i));
    }
    nex = k + 1;
    for(int i=1; i<=n; i++) {
		wie[i].push_back(par(m+2, m+2));
		sort(wie[i].begin(), wie[i].end());
	}
    for(int i=1; i<=m; i++) {
		kol[i].push_back(par(n+2, n+2));
		sort(kol[i].begin(), kol[i].end());
	}
    check(-1, -1);
    for(int i=1; i<=q; i++) {
        cin>>a>>b;
        check(a, b);
    }
    return 0;
}