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

int x_kom[4]={1,-1,0,0};
int y_kom[4]={0,0,1,-1};

vector<int> deg;
vector<pair<int,int>> pos;
vector<bool> on;
int iter=0;
map<pair<int,int>,int> points;

void zmien(int x, int y){
    if (points.find({x,y})==points.end()){
        points[{x,y}]=iter++;
        pos.push_back({x,y});
        deg.push_back(0);
        for (int i = 0; i<4; i++){
            auto it = points.find({x+x_kom[i],y+y_kom[i]});
            if (it!=points.end())deg.back()|=(on[it->second])<<i;
        }
        on.push_back(false);
    }
    int nr=points[{x,y}];
    for (int i = 0; i<4; i++){
        auto it = points.find({x+x_kom[i],y+y_kom[i]});
        if (it!=points.end())deg[it->second]^=1<<(i^1);
    }
    on[nr]=!on[nr];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int n,m,k,q;
    cin >> n >> m >> k >> q;
    for (int i = 1,x,y; i<=k; i++){
        cin >> x >> y;
        zmien(x,y);
    }
    queue<int> kol;
    vector<bool> in_queue(iter);
    for (int i = 0; i<iter; i++){
        if (on[i] && (!(deg[i]&3) || !(deg[i]>>2))){
            kol.push(i);
            in_queue[i]=true;
        }
    }
    vector<int> changed;
    while(kol.size()){
        int v = kol.front();
        kol.pop();
        in_queue[v]=false;
        changed.push_back(v);
        zmien(pos[v].first,pos[v].second);
        for (int i = 0; i<4; i++){
            auto it = points.find({pos[v].first+x_kom[i],pos[v].second+y_kom[i]});
            if (it!=points.end() && !in_queue[it->second] && (on[it->second] && (!(deg[it->second]&3) || !(deg[it->second]>>2)))){
                kol.push(it->second);
                in_queue[it->second]=true;
            }
        }
    }
    cout << changed.size() << '\n';
    while(changed.size()){
        zmien(pos[changed.back()].first,pos[changed.back()].second);
        changed.pop_back();
    }
    for (int powt = 1,x,y; powt<=q; powt++){
        cin >> x >> y;
        zmien(x,y);
        in_queue.resize(iter);
        for (int i = 0; i<iter; i++){
            if (on[i] && (!(deg[i]&3) || !(deg[i]>>2))){
                kol.push(i);
                in_queue[i]=true;
            }
        }
        while(kol.size()){
            int v = kol.front();
            kol.pop();
            changed.push_back(v);
            zmien(pos[v].first,pos[v].second);
            for (int i = 0; i<4; i++){
                auto it = points.find({pos[v].first+x_kom[i],pos[v].second+y_kom[i]});
                if (it!=points.end() && !in_queue[it->second] && (on[it->second] && (!(deg[it->second]&3) || !(deg[it->second]>>2)))){
                    kol.push(it->second);
                    in_queue[it->second]=true;
                }
            }
        }
        cout << changed.size() << '\n';
        while(changed.size()){
            zmien(pos[changed.back()].first,pos[changed.back()].second);
            changed.pop_back();
        }
    }
}