#include <bits/stdc++.h>
using namespace std;
const int64_t inf = 1e15;
// range update, point query
class bit2d {
int n, m;
vector<vector<int64_t>> bit;
public:
bit2d(int _n, int _m) : n(_n), m(_m), bit(_n + 1, vector<int64_t>(_m + 1)) {}
void add(int ix, int iy, int64_t del) {
for (ix += 1; ix > 0; ix -= ix & -ix) {
for (int y = iy + 1; y > 0; y -= y & -y) {
bit[ix][y] += del;
}
}
}
void add(int lx, int rx, int ly, int ry, int64_t del) {
add(rx, ry, del);
add(rx, ly - 1, -del);
add(lx - 1, ry, -del);
add(lx - 1, ly - 1, del);
}
int64_t query(int ix, int iy) {
int64_t ans = 0;
for (ix += 1; ix <= n; ix += ix & -ix) {
for (int y = iy + 1; y <= m; y += y & -y) {
ans += bit[ix][y];
}
}
return ans;
}
};
struct query {
int lx, rx, ly, ry, c;
};
struct pbsquery {
int i, j;
int l, r;
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m, q;
int64_t k;
cin >> n >> m >> q >> k;
vector<query> queries(q);
vector<int> buff_x, buff_y;
for (auto &[lx, rx, ly, ry, c] : queries) {
cin >> lx >> rx >> ly >> ry >> c;
--lx, --ly, --rx, --ry;
buff_x.push_back(lx), buff_x.push_back(rx);
buff_y.push_back(ly), buff_y.push_back(ry);
}
sort(buff_x.begin(), buff_x.end());
sort(buff_y.begin(), buff_y.end());
buff_x.erase(unique(buff_x.begin(), buff_x.end()), buff_x.end());
buff_y.erase(unique(buff_y.begin(), buff_y.end()), buff_y.end());
auto comp_x = [&](int i) { return lower_bound(buff_x.begin(), buff_x.end(), i) - buff_x.begin(); };
auto comp_y = [&](int i) { return lower_bound(buff_y.begin(), buff_y.end(), i) - buff_y.begin(); };
for (auto &[lx, rx, ly, ry, c] : queries) {
lx = comp_x(lx), ly = comp_y(ly), rx = comp_x(rx), ry = comp_y(ry);
}
n = buff_x.size(), m = buff_y.size();
// find for each point the query at which it gets activated
vector<vector<pbsquery>> buckets(q);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
buckets[q / 2].push_back({i, j, 0, q});
}
}
vector ans(n, vector<int>(m, q));
for (int _ = 0; _ < 13; ++_) {
vector<vector<pbsquery>> nbuckets(q);
bit2d bit(n, m);
for (int i = 0; i < q; ++i) {
auto [lx, rx, ly, ry, c] = queries[i];
bit.add(lx, rx, ly, ry, c);
for (auto &[ii, jj, l, r] : buckets[i]) {
if (bit.query(ii, jj) >= k) {
ans[ii][jj] = i;
r = i - 1;
} else {
l = i + 1;
}
if (l <= r && (l + r) / 2 < q) {
nbuckets[(l + r) / 2].push_back({ii, jj, l, r});
}
}
}
buckets = move(nbuckets);
}
vector<pair<int, pair<int, int>>> bf;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
bf.push_back({ans[i][j], {i, j}});
}
}
sort(bf.rbegin(), bf.rend());
int min_x = n, max_x = -1, min_y = m, max_y = -1;
for (int i = 0; i < q; ++i) {
while (!bf.empty() && bf.back().first <= i) {
auto [x, y] = bf.back().second;
bf.pop_back();
min_x = min(min_x, x);
min_y = min(min_y, y);
max_x = max(max_x, x);
max_y = max(max_y, y);
}
if (min_x > max_x || min_y > max_y) {
cout << "0\n";
} else {
cout << int64_t(buff_x[max_x] - buff_x[min_x] + 1) * (buff_y[max_y] - buff_y[min_y] + 1) << '\n';
}
}
}
