include <bits/stdc++.h>

using namespace std; const int N = 1e5*2+1; // 假设行列最大为1e5 int x[N], y[N];

int main() {

int n, m, q, k;
scanf("%d%d%d%d", &n, &m, &q, &k);

// 统计每行和每列的操作次数
for (int i = 0; i < q; ++i) {
    int op, c;
    scanf("%d%d", &op, &c);
    op == 1 ? x[c]++ : y[c]++;
}

// 计算行和列的余数分布
vector<int> cnt_x(k, 0), cnt_y(k, 0);
for (int i = 1; i <= n; ++i) cnt_x[x[i] % k]++;
for (int j = 1; j <= m; ++j) cnt_y[y[j] % k]++;

// 核心优化：数学公式计算满足条件的格子数
long long total = 1LL * n * m;
long long invalid = 0;
for (int a = 0; a < k; ++a) {
    int b = (k - a) % k; // 满足 (a + b) % k == 0 的余数组合
    invalid += 1LL * cnt_x[a] * cnt_y[b];
}

printf("%lld\n", total - invalid);
return 0;

}

优化思路： ‌数学建模‌

每个格子 (i, j) 的最终状态由 (x[i] + y[j]) % k 决定。 ‌关键观察‌：若 x[i] % k = a，则对应的 y[j] % k 必须为 (k - a) % k 才能使总和为 k 的倍数。 ‌空间换时间‌

用 cnt_x 和 cnt_y 数组分别统计行和列余数的出现次数。 通过遍历余数组合 (a, b)，直接计算无效格子数（总和为 k 的倍数），总有效格子数 = 总格子数 - 无效数。 ‌时间复杂度分析‌

统计行/列操作次数：O(q) 统计余数分布：O(n + m) 计算无效格子数：O(k) ‌总复杂度‌：O(n + m + q + k)，可处理 1e5 规模的数据。