#include <cstdio> #include <iostream> #include <algorithm> #include <queue> using namespace std; int n, m, Q, r, k; int d[3010][3010]; bool lak[3010][3010]; bool adj[3010][3010]; bool tr[3010][3010]; int st_ti[3010][3010]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while ('0' <= ch && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } struct node { int t, tr, x, y; bool operator < (const node & b) const { return t > b.t; } } ; priority_queue<node> q; void Init() { for (int i = 1; i <= Q; i++) { int a1, b1, a2, b2; a1 = read(); b1 = read(); a2 = read(); b2 = read(); d[a1][b1]++; d[a1][b2 + 1]--; d[a2 + 1][b1]--; d[a2 + 1][b2 + 1]++; } for (int i = 1; i <= n; i++) { int rs = 0; for (int j = 1; j <= m; j++) { rs += d[i][j]; d[i][j] = rs + d[i - 1][j]; if (d[i][j]) lak[i][j] = 1; } } for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (lak[i][j]) continue; for (int di = 0; di <= 3; di++) { int x = i + dx[di]; int y = j + dy[di]; if (x < 1 || x > n) continue; if (y < 1 || y > m) continue; if (lak[x][y]) adj[i][j] = 1; } } } void Grow(int t, int x, int y) { if (lak[x][y] || tr[x][y] || !adj[x][y]) return ; tr[x][y] = 1; st_ti[x][y] = t; q.push((node){t + k + 1, 1, x, y}); for (int i = 0; i <= 3; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 1 || nx > n) continue; if (ny < 1 || ny > m) continue; q.push((node){t + 1, 0, nx, ny}); } } void Die(int t, int x, int y) { if (!tr[x][y]) return ; if (st_ti[x][y] + k + 1 != t) return ; bool flag = false; for (int i = 0; i <= 3; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 1 || nx > n) continue; if (ny < 1 || ny > m) continue; if (lak[nx][ny]) { flag = true; return ; } if (tr[nx][ny]) { flag = true; return ; } } tr[x][y] = 0; } int main() { // freopen("lake.in", "r", stdin); // freopen("lake.out", "w", stdout); n = read(); m = read(); Q = read(); r = read(); k = read(); Init(); for (int i = 1; i <= r; i++) { int t, x, y; t = read(); x = read(); y = read(); while (q.size() && q.top().t <= t) { node tp = q.top(); q.pop(); if (tp.tr == 0) Grow(tp.t, tp.x, tp.y); else Die(tp.t, tp.x, tp.y); } if (lak[x][y] || tr[x][y]) continue; tr[x][y] = 1; st_ti[x][y] = t; q.push((node){t + k + 1, 1, x, y}); for (int j = 0; j <= 3; j++) { int nx = x + dx[j]; int ny = y + dy[j]; if (nx < 1 || nx > n) continue; if (ny < 1 || ny > m) continue; q.push((node){t + 1, 0, nx, ny}); } } while (q.size()) { node tp = q.top(); q.pop(); if (tp.tr == 0) Grow(tp.t, tp.x, tp.y); else Die(tp.t, tp.x, tp.y); } int cnt = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) if (!lak[i][j] && tr[i][j]) cnt++; printf("%d\n", cnt); // fclose(stdin); // fclose(stdout); return 0; }