#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define endl '\n'
//#pragma GCC optimize("Ofast")
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair < int, int >;
using pll = pair < ll, ll >;
const ll INF = 2e18;
const ll DIM = 200007;
const ld PI = 3.1415926535;
const int mod = 998244353;
class segTree {
public:
void build(int sz, ll x) {
this->x = x;
this->sz = sz;
T.resize(4 * sz + 7);
}
pii query() {
return {queryL(0, 0, sz - 1), queryR(0, 0, sz - 1)};
}
void update(int l, int r, ll val) {
update(0, 0, sz - 1, l, r, val);
}
private:
struct node {
ll mx, mod;
node() {
mx = 0; mod = 0;
}
node(ll mx) {
this->mx = mx;
mod = 0;
}
};
node combine(node v1, node v2) {
return {max(v1.mx, v2.mx)};
}
void apply(int val, ll x) {
T[val].mx += x;
T[val].mod += x;
}
void push(int val, int tl, int tr) {
if(T[val].mod != 0 && tl != tr) {
apply(2 * val + 1, T[val].mod);
apply(2 * val + 2, T[val].mod);
}
T[val].mod = 0;
}
void update(int val, int tl, int tr, int L, int R, ll x) {
if(L <= tl && tr <= R) {
apply(val, x);
return;
}
if(tl > R || tr < L) return;
push(val, tl, tr);
int tm = (tl + tr) >> 1;
update(2 * val + 1, tl, tm, L, R, x);
update(2 * val + 2, tm + 1, tr, L, R, x);
T[val] = combine(T[2 * val + 1], T[2 * val + 2]);
}
int queryL(int val, int tl, int tr) {
if(tl == tr) {
if(T[val].mx >= x) return tl;
else return -1;
}
push(val, tl, tr);
int tm = (tl + tr) >> 1;
if(T[2 * val + 1].mx >= x) return queryL(2 * val + 1, tl, tm);
else return queryL(2 * val + 2, tm + 1, tr);
}
int queryR(int val, int tl, int tr) {
if(tl == tr) {
if(T[val].mx >= x) return tl;
else return -1;
}
push(val, tl, tr);
int tm = (tl + tr) >> 1;
if(T[2 * val + 2].mx >= x) return queryR(2 * val + 2, tm + 1, tr);
else return queryR(2 * val + 1, tl, tm);
}
int sz;
ll x;
vector < node > T;
};
struct event {
int u, d, l, r;
ll val;
event(int u, int d, int l, int r, ll val) {
this->u = u;
this->d = d;
this->l = l;
this->r = r;
this->val = val;
}
};
vector < event > Q;
vector < int > compR, compC;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef IloveCP
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int h, w, n, x;
cin >> h >> w >> n >> x;
for(int i = 0; i < n; i++) {
int u, d, l, r;
ll val;
cin >> u >> d >> l >> r >> val;
compR.push_back(u); compR.push_back(u + 1);
compR.push_back(d); compR.push_back(d + 1);
compC.push_back(l); compC.push_back(l + 1);
compC.push_back(r); compC.push_back(r + 1);
Q.push_back({u, d, l, r, val});
}
sort(compR.begin(), compR.end());
sort(compC.begin(), compC.end());
compR.erase(unique(compR.begin(), compR.end()), compR.end());
compC.erase(unique(compC.begin(), compC.end()), compC.end());
vector < segTree > t(compR.size());
for(int i = 0; i < compR.size(); i++) {
t[i].build(compC.size(), x);
}
vector < vector < ll > > a(compR.size(), vector < ll >(compC.size(), 0));
for(int i = 0; i < n; i++) {
Q[i].u = lower_bound(compR.begin(), compR.end(), Q[i].u) - compR.begin();
Q[i].d = lower_bound(compR.begin(), compR.end(), Q[i].d) - compR.begin();
Q[i].l = lower_bound(compC.begin(), compC.end(), Q[i].l) - compC.begin();
Q[i].r = lower_bound(compC.begin(), compC.end(), Q[i].r) - compC.begin();
for(int j = Q[i].u; j <= Q[i].d; j++) {
for(int k = Q[i].l; k <= Q[i].r; k++) {
a[j][k] += Q[i].val;
}
}
bool flag = false;
int l0 = w + 1, r0 = 0, u0 = h + 1, d0 = 0;
for(int j = 0; j < compR.size() - 1; j++) {
for(int k = 0; k < compC.size(); k++) {
if(a[j][k] >= x) {
flag = true;
u0 = min(u0, compR[j]);
d0 = max(d0, compR[j + 1] - 1);
l0 = min(l0, compC[k]);
r0 = max(r0, compC[k + 1] - 1);
}
}
}
if(flag) {
//cout << l0 << " " << r0 << endl;
cout << ll(r0 - l0 + 1) * ll(d0 - u0 + 1) << endl;
}
else {
cout << 0 << endl;
}
}
return 0;
for(int i = 0; i < n; i++) {
Q[i].u = lower_bound(compR.begin(), compR.end(), Q[i].u) - compR.begin();
Q[i].d = lower_bound(compR.begin(), compR.end(), Q[i].d) - compR.begin();
Q[i].l = lower_bound(compC.begin(), compC.end(), Q[i].l) - compC.begin();
Q[i].r = lower_bound(compC.begin(), compC.end(), Q[i].r) - compC.begin();
for(int j = Q[i].u; j <= Q[i].d; j++) {
//cout << j << " " << Q[i].l << " " << Q[i].r << " " << Q[i].val << endl;
t[j].update(Q[i].l, Q[i].r, Q[i].val);
}
bool flag = false;
int l0 = w + 1, r0 = 0, u0 = h + 1, d0 = 0;
for(int j = 0; j < compR.size() - 1; j++) {
pii tmp = t[j].query();
if(tmp.first != -1) {
flag = true;
u0 = min(u0, compR[j]);
d0 = max(d0, compR[j + 1] - 1);
l0 = min(l0, compC[tmp.first]);
r0 = max(r0, compC[tmp.second + 1] - 1);
}
}
if(flag) {
//cout << l0 << " " << r0 << endl;
cout << ll(r0 - l0 + 1) * ll(d0 - u0 + 1) << endl;
}
else {
cout << 0 << endl;
}
}
return 0;
}
