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

using namespace std;

#define pii pair<int, int>

vector<pii> all_tiles, to_check;
set<pii> set_blck, used, possible, all_ins;

void add_neighbours(pii pos, vector<pii>& vec){
    pii tmp1 = pos, tmp2 = pos, tmp3 = pos, tmp4 = pos;
    tmp1.first--;
    tmp2.first++;
    tmp3.second--;
    tmp4.second++;

    if(set_blck.find(tmp1) != set_blck.end()) vec.push_back(tmp1);
    if(set_blck.find(tmp2) != set_blck.end()) vec.push_back(tmp2);
    if(set_blck.find(tmp3) != set_blck.end()) vec.push_back(tmp3);
    if(set_blck.find(tmp4) != set_blck.end()) vec.push_back(tmp4);
}

bool check_liftable(pii pos){
    pii tmp1 = pos, tmp2 = pos, tmp3 = pos, tmp4 = pos;
    tmp1.first--;
    tmp2.first++;
    tmp3.second--;
    tmp4.second++;

    bool tmp = (set_blck.find(tmp1) == set_blck.end() | possible.find(tmp1) != possible.end());
    tmp &= (set_blck.find(tmp2) == set_blck.end() | possible.find(tmp2) != possible.end());

    if(tmp) return true;

    tmp = (set_blck.find(tmp3) == set_blck.end() | possible.find(tmp3) != possible.end());
    tmp &= (set_blck.find(tmp4) == set_blck.end() | possible.find(tmp4) != possible.end());

    return tmp;
}

int propagate(){
    int out = 0;

    while(to_check.size()){
        pii tile = to_check.back();
        to_check.pop_back();
        if(used.find(tile) != used.end()) continue;
        if(check_liftable(tile)){
            used.insert(tile);
            possible.insert(tile);
            add_neighbours(tile, to_check);
            out++;
        }
    }

    return out;
}

int count_valid(){
    int out = 0;
    used.clear();
    possible.clear();
    to_check.clear();
    for(pii tile : all_tiles){
        if(set_blck.find(tile) == set_blck.end()) continue;
        if(check_liftable(tile)){
            used.insert(tile);
            possible.insert(tile);
            add_neighbours(tile, to_check);
            out++;
        } 
    }

    out += propagate();

    return out;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    int n, m, k, q;
    cin>>n>>m>>k>>q;

    for(int i = 0; i<k; i++){
        int a, b;
        cin>>a>>b;

        set_blck.insert({a, b});
        all_ins.insert({a, b});
        all_tiles.push_back({a, b});
    }

    cout<<count_valid()<<endl;

    for(int i = 0; i<q; i++){
        int a, b;
        cin>>a>>b;

        if(set_blck.find({a, b}) == set_blck.end()){
            if(all_ins.find({a, b}) == all_ins.end()){
                all_ins.insert({a, b});
                all_tiles.push_back({a, b});
            }
            set_blck.insert({a, b});
        }else{
            set_blck.erase({a, b});
        }

        cout<<count_valid()<<endl;
    }
    return 0;
}