#include <iostream>
#include <cassert>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
using ll=long long;
using ti5=tuple<int, int, int, int, ll>;
const int MN=1e4+13;
const int inf32=1e9;
const ll inf64=1e18;
int N, H, W; ll X;
vector<ti5> qry;
vector<ll> vecrow, veccol;
ll orgrow[MN], orgcol[MN];
ll minrow=inf64, maxrow=-inf64, mincol=inf64, maxcol=-inf64, val[MN][MN];
int rt[MN];
namespace seg
{
int st[MN<<11], te[MN<<11], mid[MN<<11];
ll mx[MN<<11], lz[MN<<11];
int lp[MN<<11], rp[MN<<11], idx=0;
int build(int l, int r)
{
int u=++idx;
st[u]=l; te[u]=r; mid[u]=(st[u]+te[u])>>1;
mx[u]=lz[u]=0;
return u;
}
void build(int u)
{
if (!lp[u]) lp[u]=build(st[u], mid[u]);
if (!rp[u]) rp[u]=build(mid[u]+1, te[u]);
}
void prop(int u)
{
if (!lz[u]) return;
mx[lp[u]]+=lz[u];
lz[lp[u]]+=lz[u];
mx[rp[u]]+=lz[u];
lz[rp[u]]+=lz[u];
lz[u]=0;
}
void upd(int u, int l, int r, ll x)
{
if (st[u]==l && te[u]==r)
{
mx[u]+=x;
lz[u]+=x;
return;
}
build(u);
prop(u);
if (l<=mid[u]) upd(lp[u], l, min(r, mid[u]), x);
if (r>mid[u]) upd(rp[u], max(mid[u]+1, l), r, x);
mx[u]=max(mx[lp[u]], mx[rp[u]]);
}
int qrymin(int u)
{
if (mx[u]<X) return inf32;
if (st[u]==te[u]) return st[u];
build(u);
prop(u);
if (mx[lp[u]]>=X) return qrymin(lp[u]);
else return qrymin(rp[u]);
}
int qrymax(int u)
{
if (mx[u]<X) return -inf32;
if (st[u]==te[u]) return st[u];
build(u);
prop(u);
if (mx[rp[u]]>=X) return qrymax(rp[u]);
else return qrymax(lp[u]);
}
}
int main()
{
cin>>H>>W>>N>>X;
while (N--)
{
int U, D, L, R; ll C; cin>>U>>D>>L>>R>>C; D++; R++;
vecrow.push_back(U); vecrow.push_back(D);
veccol.push_back(L); veccol.push_back(R);
qry.push_back({U, D, L, R, C});
}
sort(vecrow.begin(), vecrow.end());
vecrow.erase(unique(vecrow.begin(), vecrow.end()), vecrow.end());
sort(veccol.begin(), veccol.end());
veccol.erase(unique(veccol.begin(), veccol.end()), veccol.end());
for (auto &[U, D, L, R, C]:qry)
{
int o;
o=U;
U=lower_bound(vecrow.begin(), vecrow.end(), U)-vecrow.begin()+1;
orgrow[U]=o;
o=D;
D=lower_bound(vecrow.begin(), vecrow.end(), D)-vecrow.begin()+1;
orgrow[D]=o;
o=L;
L=lower_bound(veccol.begin(), veccol.end(), L)-veccol.begin()+1;
orgcol[L]=o;
o=R;
R=lower_bound(veccol.begin(), veccol.end(), R)-veccol.begin()+1;
orgcol[R]=o;
}
for (int i=1; i<MN; i++) rt[i]=seg::build(1, MN-1);
//cerr<<"HERE"<<endl;
for (auto &[U, D, L, R, C]:qry)
{
for (int i=U; i<D; i++)
{
//cerr<<i<<": "<<L<<" TO "<<R-1<<endl;
seg::upd(rt[i], L, R-1, C);
//cerr<<"DONE"<<endl;
int minj=seg::qrymin(rt[i]), maxj=seg::qrymax(rt[i]);
//cerr<<"DONE"<<endl;
if (minj==inf32)
{
assert(maxj==-inf32);
continue;
}
minrow=min(minrow, orgrow[i]);
maxrow=max(maxrow, orgrow[i+1]-1);
mincol=min(mincol, orgcol[minj]);
maxcol=max(maxcol, orgcol[maxj+1]-1);
}
if (minrow==inf64) cout<<0<<endl;
else cout<<(maxrow-minrow+1)*(maxcol-mincol+1)<<endl;
}
return 0;
}
