unuzero

#include <fstream>
#include <vector>
#include <unordered_map>
using namespace std;

ifstream fin("unuzero.in");
ofstream fout("unuzero.out");

vector<int> par;
int gasit(int x) { while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; } return x; }
void uneste(int a, int b) { a = gasit(a); b = gasit(b); if (a != b) par[a] = b; }

long long M, N, K, Q;
vector<long long> P;

long long countComp(int blocks) {
    int total = (int)Q * blocks;
    par.assign(total, 0);
    for (int i = 0; i < total; i++) par[i] = i;
    unordered_map<long long, int> mp;
    mp.reserve(total * 2);
    vector<long long> rr(total), cc(total);
    auto key = [&](long long r, long long c) { return r * (N + 1) + c; };
    for (int b = 0; b < blocks; b++)
        for (int q = 0; q < Q; q++) {
            long long r = (P[q] - 1) / N + (long long)b * M;
            long long c = (P[q] - 1) % N;
            int id = b * (int)Q + q;
            rr[id] = r; cc[id] = c; mp[key(r, c)] = id;
        }
    for (int id = 0; id < total; id++) {
        long long r = rr[id], c = cc[id];
        if (c + 1 < N) { auto it = mp.find(key(r, c + 1)); if (it != mp.end()) uneste(id, it->second); }
        { auto it = mp.find(key(r + 1, c)); if (it != mp.end()) uneste(id, it->second); }
    }
    long long comp = 0;
    for (int id = 0; id < total; id++) if (gasit(id) == id) comp++;
    return comp;
}

int main() {
    fin >> M >> N >> K >> Q;
    P.resize(Q);
    for (auto &x : P) fin >> x;
    long long c1 = countComp(1);
    long long c2 = (K >= 2) ? countComp(2) : c1;
    fout << c1 * K - (2 * c1 - c2) * (K - 1) << "\n";
    return 0;
}