#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int s, e, m, v, lazy;
node* l = nullptr, * r = nullptr;
node(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(0), lazy(0) {}
void prop() {
if (s == e) return;
if (!l)
l = new node(s, m),
r = new node(m + 1, e);
if (lazy == 0) return;
l->v += lazy;
r->v += lazy;
l->lazy += lazy;
r->lazy += lazy;
lazy = 0;
}
void upd(int a, int b, int x) {
if (b < s || a > e) return;
if (a <= s && b >= e) {
v += x;
lazy += x;
return;
}
prop();
l->upd(a, b, x);
r->upd(a, b, x);
v = max(l->v, r->v);
}
} *root;
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int H, W, N, X, a, b, c, d, e; cin >> H >> W >> N >> X;
root = new node(0, 2 * N - 1);
vector<int> x1, x2, y1, y2, ux, uy, C;
for (int i = 0; i < N; i++) {
cin >> a >> b >> c >> d >> e;
x1.push_back(a);
x2.push_back(b);
y1.push_back(c);
y2.push_back(d);
ux.push_back(a);
ux.push_back(b);
uy.push_back(c);
uy.push_back(d);
C.push_back(e);
}
sort(ux.begin(), ux.end());
ux.erase(unique(ux.begin(), ux.end()), ux.end());
sort(uy.begin(), uy.end());
uy.erase(unique(uy.begin(), uy.end()), uy.end());
for (int i = 0; i < N; i++) {
x1[i] = lower_bound(ux.begin(), ux.end(), x1[i]) - ux.begin();
x2[i] = lower_bound(ux.begin(), ux.end(), x2[i]) - ux.begin();
y1[i] = lower_bound(uy.begin(), uy.end(), y1[i]) - uy.begin();
y2[i] = lower_bound(uy.begin(), uy.end(), y2[i]) - uy.begin();
}
vector<vector<int>> rows1(2 * N, vector<int>()), rows2(2 * N, vector<int>()), cols1(2 * N, vector<int>()), cols2(2 * N, vector<int>());
for (int i = 0; i < N; i++) {
rows1[x1[i]].push_back(i);
rows2[x2[i]].push_back(i);
cols1[y1[i]].push_back(i);
cols2[y2[i]].push_back(i);
}
vector<pair<pair<int, int>, pair<int, int>>> vals(N, pair<pair<int, int>, pair<int, int>>(pair<int, int>(-1, -1), pair<int, int>(-1, -1)));
int crntt = N - 1;
for (int i = 0; i < 2 * N; i++) {
for (int j : rows1[i]) if (j <= crntt) root->upd(y1[j], y2[j], C[j]);
while (root->v >= X) {
vals[crntt].first.first = i;
if (x1[crntt] <= i && i <= x2[crntt]) root->upd(y1[crntt], y2[crntt], -C[crntt]);
crntt--;
}
for (int j : rows2[i]) if (j <= crntt) root->upd(y1[j], y2[j], -C[j]);
}
root->upd(0, 2 * N - 1, 0);
crntt = N - 1;
for (int i = 2 * N - 1; i >= 0; i--) {
for (int j : rows2[i]) if (j <= crntt) root->upd(y1[j], y2[j], C[j]);
while (root->v >= X) {
vals[crntt].first.second = i;
if (x1[crntt] <= i && i <= x2[crntt]) root->upd(y1[crntt], y2[crntt], -C[crntt]);
crntt--;
}
for (int j : rows1[i]) if (j <= crntt) root->upd(y1[j], y2[j], -C[j]);
}
root->upd(0, 2 * N - 1, 0);
crntt = N - 1;
for (int i = 0; i < 2 * N; i++) {
for (int j : cols1[i]) if (j <= crntt) root->upd(x1[j], x2[j], C[j]);
while (root->v >= X) {
vals[crntt].second.first = i;
if (y1[crntt] <= i && i <= y2[crntt]) root->upd(x1[crntt], x2[crntt], -C[crntt]);
crntt--;
}
for (int j : cols2[i]) if (j <= crntt) root->upd(x1[j], x2[j], -C[j]);
}
root->upd(0, 2 * N - 1, 0);
crntt = N - 1;
for (int i = 2 * N - 1; i >= 0; i--) {
for (int j : cols2[i]) if (j <= crntt) root->upd(x1[j], x2[j], C[j]);
while (root->v >= X) {
vals[crntt].second.second = i;
if (y1[crntt] <= i && i <= y2[crntt]) root->upd(x1[crntt], x2[crntt], -C[crntt]);
crntt--;
}
for (int j : cols1[i]) if (j <= crntt) root->upd(x1[j], x2[j], -C[j]);
}
for (int i = 0; i < N; i++) {
if (vals[i].first.first == -1) cout << 0 << '\n';
else cout << (ux[vals[i].first.second] - ux[vals[i].first.first] + 1) * (uy[vals[i].second.second] - uy[vals[i].second.first] + 1) << '\n';
}
}
