#include <bits/stdc++.h>
using namespace std;
struct query {
int lx, rx, ly, ry, c;
};
const int64_t inf = 1e15;
class lazy_segment_tree {
int n;
vector<int64_t> seg, lazy;
void push(int v) {
seg[v] += lazy[v];
if (v < 2 * n) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
void pull(int v) {
seg[v] = max(seg[2 * v], seg[2 * v + 1]);
}
void add(int v, int tl, int tr, int l, int r, int64_t del) {
push(v);
if (tr < l || r < tl) return;
if (l <= tl && tr <= r) {
lazy[v] += del;
push(v);
return;
}
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r, del);
add(2 * v + 1, tm + 1, tr, l, r, del);
pull(v);
}
int64_t query(int v, int tl, int tr, int l, int r) {
push(v);
if (tr < l || r < tl) return -inf;
if (l <= tl && tr <= r) return seg[v];
int tm = (tl + tr) / 2;
return max(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
}
public:
lazy_segment_tree(int n) : n(n), seg(4 * n), lazy(4 * n) {}
void add(int l, int r, int64_t del) { add(1, 0, n - 1, l, r, del); }
int64_t query(int l, int r) { return query(1, 0, n - 1, l, r); }
};
vector<int64_t> solve(int n, int m, int q, int64_t k, vector<query> queries) {
vector<int> buff_x, buff_y;
for (auto &[lx, rx, ly, ry, c] : queries) {
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();
int ptr = m;
lazy_segment_tree st(n);
vector<vector<pair<pair<int, int>, int64_t>>> events(m);
bool flag = true;
auto add_event = [&](int i, int64_t del, int l, int r) {
if (i < 0 || i >= m) return;
events[i].push_back({{l, r}, del});
if (flag && i >= ptr || !flag && i <= ptr) {
st.add(l, r, del);
}
};
auto push_rect = [&](int i, int mult) {
auto [lx, rx, ly, ry, c] = queries[i];
if (flag) {
add_event(ry, mult * c, lx, rx);
add_event(ly - 1, -mult * c, lx, rx);
} else {
add_event(ly, mult * c, lx, rx);
add_event(ry + 1, -mult * c, lx, rx);
}
};
auto apply_events = [&]() {
for (auto &[r, del] : events[ptr]) {
st.add(r.first, r.second, del);
}
};
vector<int> r(q);
for (int i = q - 1; i >= 0; --i) {
push_rect(i, 1);
}
for (int i = q - 1; i >= 0; --i) {
while (ptr != -1 && st.query(0, n - 1) < k) {
ptr--;
if (ptr != -1) apply_events();
}
r[i] = ptr;
push_rect(i, -1);
}
events = vector<vector<pair<pair<int, int>, int64_t>>>(m);
st = lazy_segment_tree(n);
ptr = -1;
flag = false;
vector<int> l(q);
for (int i = q - 1; i >= 0; --i) {
push_rect(i, 1);
}
for (int i = q - 1; i >= 0; --i) {
while (ptr != m && st.query(0, n - 1) < k) {
ptr++;
if (ptr != m) apply_events();
}
l[i] = ptr;
push_rect(i, -1);
}
vector<int64_t> ans(q);
for (int i = 0; i < q; ++i) {
if (l[i] <= r[i]) {
ans[i] = buff_y[r[i]] - buff_y[l[i]] + 1;
}
}
return ans;
}
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);
for (auto &[lx, rx, ly, ry, c] : queries) {
cin >> lx >> rx >> ly >> ry >> c;
--lx, --ly, --rx, --ry;
}
auto ans1 = solve(n, m, q, k, queries);
swap(n, m);
for (auto &[lx, rx, ly, ry, c] : queries) {
swap(lx, ly), swap(rx, ry);
}
auto ans2 = solve(n, m, q, k, queries);
for (int i = 0; i < q; ++i) {
cout << ans1[i] * ans2[i] << '\n';
}
}
