#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
struct SegTree {
int aint[4 * N + 5];
int lazy[4 * N + 4];
int n;
SegTree(int _n) {
n = _n;
}
void propag(int x) {
aint[x] += lazy[x];
if (2 * x + 1 < 4 * N + 5) {
lazy[2 * x] += lazy[x];
lazy[2 * x + 1] += lazy[x];
}
lazy[x] = 0;
}
void update(int pos, int st, int dr, int l, int r, int val) {
propag(pos);
if (l <= st && dr <= r) {
lazy[pos] += val;
propag(pos);
return;
}
int mid = (st + dr) / 2;
if (l <= mid) {
update(2 * pos, st, mid, l, r, val);
} else {
propag(2 * pos);
}
if (mid < r) {
update(2 * pos + 1, mid + 1, dr, l, r, val);
} else {
propag(2 * pos + 1);
}
aint[pos] = max(aint[2 * pos], aint[2 * pos + 1]);
}
int query() {
propag(1);
return aint[1];
}
};
vector<int> u, d, l, r, c;
vector<vector<int>> rasp;
int h, w, n, x;
void calc(int unde) {
rasp[unde].resize(n, 0);
vector<int> norm;
vector<bool> enter(n, false), exit(n, false);
for (int i = 0; i < n; i ++) {
norm.push_back(l[i]);
norm.push_back(r[i]);
}
sort(norm.begin(), norm.end());
norm.erase(unique(norm.begin(), norm.end()), norm.end());
auto binara = [&] (int _x) -> int {
int pos = 0;
for (int pas = 1 << 20; pas; pas >>= 1) {
if (pos + pas < (int)norm.size() && norm[pos + pas] <= _x) {
pos += pas;
}
}
return pos + 1;
};
vector<pair<int, int>> ev;
for (int i = 0; i < n; i ++) {
ev.push_back({u[i], i});
ev.push_back({d[i] + 1, -i - 1});
}
sort(ev.begin(), ev.end());
int ans = n;
SegTree ds(norm.size());
for (auto i : ev) {
if (i.second >= 0) {
enter[i.second] = true;
if (i.second >= ans) {
continue;
}
ds.update(1, 1, norm.size(), binara(l[i.second]), binara(r[i.second]), c[i.second]);
} else {
i.second = -i.second - 1;
exit[i.second] = true;
if (i.second >= ans) {
continue;
}
ds.update(1, 1, norm.size(), binara(l[i.second]), binara(r[i.second]), -c[i.second]);
}
while (ds.query() >= x) {
ans --;
rasp[unde][ans] = i.first;
if (enter[ans] && !exit[ans]) {
ds.update(1, 1, norm.size(), binara(l[ans]), binara(r[ans]), -c[ans]);
}
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> h >> w >> n >> x;
u.resize(n);
d.resize(n);
l.resize(n);
r.resize(n);
c.resize(n);
rasp.resize(4);
for (int i = 0; i < n; i ++) {
cin >> u[i] >> d[i] >> l[i] >> r[i] >> c[i];
}
vector<int> ans(n);
for (auto i : {0, 1, 2, 3}) {
calc(i);
auto nu = r;
auto nr = d;
auto nd = l;
auto nl = u;
for (auto &i : nu) {
i = w - i + 1;
}
for (auto &i : nd) {
i = w - i + 1;
}
u = nu;
r = nr;
d = nd;
l = nl;
swap(w, h);
}
for (int i = 0; i < n; i ++) {
if (rasp[0][i] == 0 || rasp[1][i] == 0) {
cout << 0 << '\n';
} else {
cout << 1ll * (h - rasp[2][i] - rasp[0][i] + 2) * (w - rasp[1][i] - rasp[3][i] + 2) << '\n';
}
}
}
/*
vreau cel mai de sus pentru care, la timpul i, are suma >= x
baleiez de sus in jos
*/
