#include <bits/stdc++.h>
using namespace std;
#define int long long
struct rain {
int u, d, l, r, val;
};
struct upd {
int h, l, r, val, id;
bool operator < (const upd &b) const {
return h < b.h;
}
};
const int maxn = 4e5 + 5, maxN = 2e6 + 5, INF = 1e9;
int n, m, k, X;
vector<rain> a;
vector<int> vals;
int dc(int x) {return lower_bound(vals.begin(), vals.end(), x) - vals.begin();}
int seg[maxN], lazy[maxN];
void build(int id, int l, int r) {
seg[id] = lazy[id] = 0;
if (l == r) return;
int mid = (l+r)/2;
build(id*2, l, mid); build(id*2, mid+1, r);
}
void push(int id) {
seg[id] += lazy[id];
if (id*2 < maxN) lazy[id*2] += lazy[id];
if (id*2+1 < maxN) lazy[id*2+1] += lazy[id];
lazy[id] = 0;
}
void update(int id, int l, int r, int findl, int findr, int val) {
push(id);
if (r < findl || findr < l) return;
if (findl <= l && r <= findr) {
lazy[id] += val;
push(id);
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, findl, findr, val);
update(id*2+1, mid+1, r, findl, findr, val);
seg[id] = max(seg[id*2], seg[id*2+1]);
}
int mx() {
return seg[1];
}
vector<upd> vec;
vector<int> solve() {
int pt = 0;
vals = {0};
vec.clear();
for (auto [u, d, l, r, val]:a) {
vec.push_back({u, l, r, val, pt});
vec.push_back({d+1, l, r, -val, pt});
vals.push_back(l); vals.push_back(r);
pt++;
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int sz = (int)vals.size() - 1;
sort(vec.begin(), vec.end());
build(1, 1, sz);
int lasth = -1;
vector<int> ans(k, INF);
for (auto [h, l, r, val, id]:vec) {
if (h != lasth) {
while (mx() >= X) {
pt--;
ans[pt] = lasth;
if (a[pt].u <= lasth && lasth <= a[pt].d) {
update(1, 1, sz, dc(a[pt].l), dc(a[pt].r), -a[pt].val);
}
}
lasth = h;
}
if (id < pt) {
update(1, 1, sz, dc(l), dc(r), val);
}
}
for (int i=1;i<k;i++) ans[i] = min(ans[i], ans[i-1]);
return ans;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m >> k >> X;
a.resize(k);
for (auto &[u, d, l, r, val]:a) cin >> u >> d >> l >> r >> val;
vector<int> ans[4];
for (int i=0;i<4;i++) {
ans[i] = solve();
for (auto &[u, d, l, r, val]:a) {
swap(u, l); swap(l, d); swap(d, r);
l = n - l + 1, r = n - r + 1;
}
swap(n, m);
}
for (int i=0;i<k;i++) {
int h, w;
if (ans[0][i] == INF) h = 0;
else h = (n - ans[2][i] + 1) - ans[0][i] + 1;
if (ans[1][i] == INF) w = 0;
else w = (m - ans[3][i] + 1) - ans[1][i] + 1;
cout << h * w << "\n";
}
}
