#include <cstdio> #include <iostream> #include <algorithm> #include <queue> using namespace std; int n, m, Q, r, k; int d[3010][3010]; int lak[3010][3010]; int adj[3010][3010]; int tr[3010][3010]; int st_ti[3010][3010]; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; 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; cin >> a1 >> b1 >> a2 >> b2; 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 d = 0; d <= 3; d++) { int x = i + dx[d]; int y = j + dy[d]; 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; if (tr[nx][ny]) flag = true; } if (!flag) tr[x][y] = 0; } int main() { // freopen("lake.in", "r", stdin); // freopen("lake.out", "w", stdout); cin >> n >> m >> Q >> r >> k; Init(); for (int i = 1; i <= r; i++) { int t, x, y; cin >> t >> x >> y; 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++; cout << cnt << endl; fclose(stdin); fclose(stdout); return 0; }