#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll h, w, n, x;
int a[200005][5];
int u[200005], d[200005], l[200005], rrr[200005];
int U[200005], D[200005], L[200005], R[200005];
vector < tuple <int, int, int, int> > s[1400005];
struct node {
int s, e, m;
ll val, lz;
node *l, *r;
node (int _s, int _e) {
s = _s, e = _e, m = (s + e) >> 1;
if (s != e) l = new node(s, m), r = new node(m + 1, e);
val = lz = 0;
}
void prop() {
if (lz) {
val += lz;
if (s != e) l->lz += lz, r->lz += lz;
lz = 0;
}
}
void upd (int a, int b, ll c) {
if (a == s && b == e) lz += c;
else {
if (b <= m) l->upd(a, b, c);
else if (a > m) r->upd(a, b, c);
else l->upd(a, m, c), r->upd(m + 1, b, c);
l->prop(), r->prop();
val = max(l->val, r->val);
}
}
ll qry() {
prop();
return val;
}
}*root;
long long t[1<<23], lazy[1<<23];
void build(int v, int tl, int tr){
if(tl == tr)t[v] = 0;
else {
build(v<<1, tl, (tl+tr)>>1);
build(v<<1|1, ((tl+tr)>>1) + 1, tr);
t[v] = max(t[v<<1], t[v<<1|1]);
}
lazy[v] = 0;
}
inline void push(int v, int tl, int tr) {
int tm = (tl + tr) >> 1;
t[v<<1] += lazy[v];
lazy[v<<1] += lazy[v];
t[(v<<1)+1] += lazy[v];
lazy[(v<<1)+1] += lazy[v];
lazy[v] = 0;
}
inline void update(int v, int tl, int tr, int l, int r, ll addend) {
if (l > r)
return;
push(v, tl, tr);
if (l == tl && tr == r) {
t[v] += addend;
lazy[v] += addend;
} else {
push(v, tl, tr);
int tm = (tl + tr) >> 1;
update(v<<1, tl, tm, l, min(r, tm), addend);
update((v<<1)+1, tm+1, tr, max(l, tm+1), r, addend);
t[v] = max(t[v<<1], t[(v<<1)+1]);
}
}
inline long long query(int v, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && tr == r)
return t[v];
push(v, tl, tr);
int tm = (tl + tr) >> 1;
return max(query(v<<1, tl, tm, l, min(r, tm)),
query((v<<1)+1, tm+1, tr, max(l, tm+1), r));
}
int main () {
ios::sync_with_stdio(0); cin.tie(0);
cin >> h >> w >> n >> x;
vector <int> r, c;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 5; j++) {
cin >> a[i][j];
if (j < 2) r.push_back(a[i][j]), r.push_back(a[i][j] - 1), r.push_back(a[i][j] + 1);
else if (j < 4) c.push_back(a[i][j]), c.push_back(a[i][j] - 1), c.push_back(a[i][j] + 1);
}
}
sort(r.begin(), r.end());
sort(c.begin(), c.end());
r.erase(unique(r.begin(), r.end()), r.end());
c.erase(unique(c.begin(), c.end()), c.end());
for (int i = 1; i <= n; i++) {
U[i] = lower_bound(r.begin(), r.end(), a[i][0]) - r.begin() + 1;
D[i] = lower_bound(r.begin(), r.end(), a[i][1] + 1) - r.begin() + 1;
L[i] = lower_bound(c.begin(), c.end(), a[i][2]) - c.begin() + 1;
R[i] = lower_bound(c.begin(), c.end(), a[i][3]) - c.begin() + 1;
s[U[i]].push_back({L[i], R[i], i, a[i][4]});
s[D[i]].push_back({L[i], R[i], i, -a[i][4]});
}
//root = new node(1, (int)c.size());
const int lim = n * 6;
build(1, 1, lim);
int ptr = 1;
for (auto i : s[ptr]) {
int a, b, c, d;
tie (a, b, c, d) = i;
//root->upd(a, b, d);
update(1, 1, lim, a, b, d);
}
for (int i = n; i >= 1; i--) {
if (U[i + 1] <= ptr && ptr < D[i + 1]) {
//root->upd(L[i + 1], R[i + 1], -a[i + 1][4]);
update(1, 1, lim, L[i + 1], R[i + 1], -a[i + 1][4]);
}
while (ptr <= (int)r.size() && query(1, 1, lim, 1, lim) < x) {
ptr++;
for (auto j : s[ptr]) {
int a, b, c, d;
tie (a, b, c, d) = j;
if (c > i) continue;
//root->upd(a, b, d);
update(1, 1, lim, a, b, d);
}
}
u[i] = ptr;
}
cerr << "w\n";
for (int i = 1; i <= (int)r.size(); i++) s[i].clear();
for (int i = 1; i <= n; i++) {
U[i] = lower_bound(r.begin(), r.end(), a[i][0] - 1) - r.begin() + 1;
D[i] = lower_bound(r.begin(), r.end(), a[i][1]) - r.begin() + 1;
//L[i] = lower_bound(c.begin(), c.end(), a[i][2]) - c.begin() + 1;
//R[i] = lower_bound(c.begin(), c.end(), a[i][3]) - c.begin() + 1;
s[U[i]].push_back({L[i], R[i], i, -a[i][4]});
s[D[i]].push_back({L[i], R[i], i, a[i][4]});
}
//root = new node(1, (int)c.size());
build(1, 1, lim);
ptr = (int)r.size();
for (auto i : s[ptr]) {
int a, b, c, d;
tie (a, b, c, d) = i;
//root->upd(a, b, d);
update(1, 1, lim, a, b, d);
}
for (int i = n; i >= 1; i--) {
if (U[i + 1] < ptr && ptr <= D[i + 1]) update(1, 1, lim, L[i + 1], R[i + 1], -a[i + 1][4]);
while (ptr >= 1 && query(1, 1, lim, 1, lim) < x) {
ptr--;
for (auto j : s[ptr]) {
int a, b, c, d;
tie (a, b, c, d) = j;
if (c > i) continue;
//root->upd(a, b, d);
update(1, 1, lim, a, b, d);
}
}
d[i] = ptr;
}
cerr << "w\n";
for (int i = 1; i <= (int)r.size(); i++) s[i].clear();
for (int i = 1; i <= n; i++) {
U[i] = lower_bound(r.begin(), r.end(), a[i][0]) - r.begin() + 1;
D[i] = lower_bound(r.begin(), r.end(), a[i][1]) - r.begin() + 1;
L[i] = lower_bound(c.begin(), c.end(), a[i][2]) - c.begin() + 1;
R[i] = lower_bound(c.begin(), c.end(), a[i][3] + 1) - c.begin() + 1;
s[L[i]].push_back({U[i], D[i], i, a[i][4]});
s[R[i]].push_back({U[i], D[i], i, -a[i][4]});
}
//root = new node(1, (int)r.size());
build(1, 1, lim);
ptr = 1;
for (auto i : s[ptr]) {
int a, b, cc, d;
tie (a, b, cc, d) = i;
//root->upd(a, b, d);
update(1, 1, lim, a, b, d);
}
for (int i = n; i >= 1; i--) {
if (L[i + 1] <= ptr && ptr < R[i + 1]) update(1, 1, lim, U[i + 1], D[i + 1], -a[i + 1][4]);
while (ptr <= (int)c.size() && query(1, 1, lim, 1, lim) < x) {
ptr++;
for (auto j : s[ptr]) {
int a, b, cc, d;
tie (a, b, cc, d) = j;
if (cc > i) continue;
//root->upd(a, b, d);
update(1, 1, lim, a, b, d);
}
}
l[i] = ptr;
}
cerr << "w\n";
for (int i = 1; i <= (int)c.size(); i++) s[i].clear();
for (int i = 1; i <= n; i++) {
//U[i] = lower_bound(r.begin(), r.end(), a[i][0]) - r.begin() + 1;
//D[i] = lower_bound(r.begin(), r.end(), a[i][1]) - r.begin() + 1;
L[i] = lower_bound(c.begin(), c.end(), a[i][2] - 1) - c.begin() + 1;
R[i] = lower_bound(c.begin(), c.end(), a[i][3]) - c.begin() + 1;
s[L[i]].push_back({U[i], D[i], i, -a[i][4]});
s[R[i]].push_back({U[i], D[i], i, a[i][4]});
}
//root = new node(1, (int)r.size());
build(1, 1, lim);
ptr = (int)c.size();
for (auto i : s[ptr]) {
int a, b, cc, d;
tie (a, b, cc, d) = i;
//root->upd(a, b, d);
update(1, 1, lim, a, b, d);
}
for (int i = n; i >= 1; i--) {
if (L[i + 1] < ptr && ptr <= R[i + 1]) update(1, 1, lim, U[i + 1], D[i + 1], -a[i + 1][4]);
while (ptr >= 1 && query(1, 1, lim, 1, lim) < x) {
ptr--;
for (auto j : s[ptr]) {
int a, b, cc, d;
tie (a, b, cc, d) = j;
if (cc > i) continue;
//root->upd(a, b, d);
update(1, 1, lim, a, b, d);
}
}
rrr[i] = ptr;
}
for (int i = 1; i <= n; i++) {
//cout << u[i] << ' ' << d[i] << ' ' << l[i] << ' ' << r[i] << ' ' << r[d[i] - 1] << ' ' << r[u[i] - 1] << '\n';
if (d[i] >= u[i] && rrr[i] >= l[i]) {
cout << 1ll * (r[d[i] - 1] - r[u[i] - 1] + 1) * (c[rrr[i] - 1] - c[l[i] - 1] + 1) << '\n';
}
else cout << 0 << '\n';
}
}
