#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
const int M=1e6+10;
const int K=1<<20;
struct uwu{
vector<ll> s,lz;
void init(){
s.resize(K),lz.resize(K);
}
void build(int l,int r,int idx){
s[idx]=0,lz[idx]=0;
if(l==r) return;
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
}
void pushlz(int l,int r,int idx){
if(lz[idx]==0) return;
s[idx]+=lz[idx];
if(l!=r) lz[idx*2]+=lz[idx],lz[idx*2+1]+=lz[idx];
lz[idx]=0;
}
void update(int l,int r,int idx,int a,int b,ll val){
pushlz(l,r,idx);
if(a>r || b<l) return;
if(a<=l && b>=r){
lz[idx]+=val;
pushlz(l,r,idx);
return;
}
int m=(l+r)/2;
update(l,m,idx*2,a,b,val);
update(m+1,r,idx*2+1,a,b,val);
s[idx]=max(s[idx*2],s[idx*2+1]);
}
ll query(int l,int r,int idx,int a,int b){
pushlz(l,r,idx);
if(a>r || b<l) return 0;
if(a<=l && b>=r) return s[idx];
int m=(l+r)/2;
return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
}
}T;
ll ta[N],tb[N],tc[N],td[N],ui[N],di[N],li[N],ri[N],wi[N];
int out[N];
int ti,cnt;
vector<tuple<ll,ll,ll,ll,int>> ev;
vector<tuple<ll,ll,ll>> cont[N];
//column, [l,r], +val, time
vector<ll> cr,cc;
int fdr(ll x){return lower_bound(cr.begin(),cr.end(),x)-cr.begin();}
int fdc(ll x){return lower_bound(cc.begin(),cc.end(),x)-cc.begin();}
int main(){
T.init();
ll h,w,x; int n; cin>>h >>w >>n >>x;
for(int i=1;i<=n;i++){
ll u,d,l,r,w; cin>>u >>d >>l >>r >>w;
ui[i]=u,di[i]=d,li[i]=l,ri[i]=r,wi[i]=w;
cr.push_back(u);
cr.push_back(d);
cc.push_back(l);
cc.push_back(r);
}
sort(cr.begin(),cr.end());
sort(cc.begin(),cc.end());
cr.erase(unique(cr.begin(),cr.end()),cr.end());
cc.erase(unique(cc.begin(),cc.end()),cc.end());
int szr=cr.size(),szc=cc.size();
cnt++;
int id=0;
for(int i=1;i<=n;i++){
ev.push_back({ui[i],li[i],ri[i],wi[i],i});
ev.push_back({di[i]+1,li[i],ri[i],-wi[i],i});
}
sort(ev.begin(),ev.end());
int ti=n;
T.build(0,szc-1,1);
for(int i=0;i<szr;i++){
while(id<ev.size() && get<0>(ev[id])<=cr[i]){
auto [u,l,r,w,c]=ev[id++];
if(out[c]==cnt) continue;
//cout<<"add" <<l <<" " <<r <<" " <<w <<"\n";
cont[c].push_back({fdc(l),fdc(r),w});
T.update(0,szc-1,1,fdc(l),fdc(r),w);
}
while(T.query(0,szc-1,1,0,szc-1)>=x && ti){
ta[ti]=cr[i];
out[ti]=cnt;
for(auto [l,r,w]:cont[ti]) T.update(0,szc-1,1,l,r,-w);
ti--;
}
//cout<<cr[i] <<"\n";
// for(int i=0;i<szc;i++){
// cout<<cc[i] <<" ";
// cout<<T.query(0,szc-1,1,i,i) <<"\n";
// }
if(ti==0) break;
}
// for(int i=1;i<=n;i++) cout<<ta[i] <<" ";
// cout<<"\n";
for(int i=1;i<=n;i++) cont[i].clear();
ev.clear();
for(int i=1;i<=n;i++){
ev.push_back({ui[i]-1,li[i],ri[i],-wi[i],i});
ev.push_back({di[i],li[i],ri[i],wi[i],i});
}
sort(ev.begin(),ev.end(),greater<tuple<ll,ll,ll,ll,int>>());
ti=n;
cnt++;
id=0;
T.build(0,szc-1,1);
for(int i=szr-1;i>=0;i--){
while(id<ev.size() && get<0>(ev[id])>=cr[i]){
auto [u,l,r,w,c]=ev[id++];
if(out[c]==cnt) continue;
//cout<<c <<" " <<out[c] <<" " <<cnt <<"\n";
//cout<<"add" <<l <<" " <<r <<" " <<w <<"\n";
cont[c].push_back({fdc(l),fdc(r),w});
T.update(0,szc-1,1,fdc(l),fdc(r),w);
}
while(T.query(0,szc-1,1,0,szc-1)>=x && ti){
tb[ti]=cr[i];
//cout<<"set";
//cout<<ti <<" " <<cnt <<"\n";
out[ti]=cnt;
//cout<<"set";
//cout<<ti <<" " <<cnt <<"\n";
//cout<<out[5] <<"\n";
for(auto [l,r,w]:cont[ti]){
//cout<<"rem" <<l <<" " <<r <<" " <<w <<"\n";
T.update(0,szc-1,1,l,r,-w);
}
ti--;
}
//cout<<"sp" <<out[5] <<"\n";
//cout<<cr[i] <<"\n";
// for(int i=0;i<szc;i++){
// cout<<cc[i] <<" ";
// cout<<T.query(0,szc-1,1,i,i) <<"\n";
// }
// cout<<"ck";
// for(int i=1;i<=n;i++) cout<<out[i] <<" ";
// cout<<"\n";
if(ti==0) break;
}
// for(int i=1;i<=n;i++){
// cout<<ta[i] <<" " <<tb[i] <<"\n";
// }
ev.clear(),ti=n,cnt++,id=0;
cr.clear(),cc.clear();
for(int i=1;i<=n;i++) cont[i].clear();
for(int i=1;i<=n;i++) swap(ui[i],li[i]),swap(di[i],ri[i]);
for(int i=1;i<=n;i++){
ll u=ui[i],d=di[i],l=li[i],r=ri[i],w=wi[i];
cr.push_back(u);
cr.push_back(d);
cc.push_back(l);
cc.push_back(r);
}
sort(cr.begin(),cr.end());
sort(cc.begin(),cc.end());
cr.erase(unique(cr.begin(),cr.end()),cr.end());
cc.erase(unique(cc.begin(),cc.end()),cc.end());
szr=cr.size(),szc=cc.size();
cnt++;
id=0;
for(int i=1;i<=n;i++){
ev.push_back({ui[i],li[i],ri[i],wi[i],i});
ev.push_back({di[i]+1,li[i],ri[i],-wi[i],i});
}
sort(ev.begin(),ev.end());
ti=n;
T.build(0,szc-1,1);
for(int i=0;i<szr;i++){
while(id<ev.size() && get<0>(ev[id])<=cr[i]){
auto [u,l,r,w,c]=ev[id++];
if(out[c]==cnt) continue;
cont[c].push_back({fdc(l),fdc(r),w});
T.update(0,szc-1,1,fdc(l),fdc(r),w);
}
while(T.query(0,szc-1,1,0,szc-1)>=x && ti){
tc[ti]=cr[i];
out[ti]=cnt;
for(auto [l,r,w]:cont[ti]) T.update(0,szc-1,1,l,r,-w);
ti--;
}
if(ti==0) break;
}
for(int i=1;i<=n;i++) cont[i].clear();
ev.clear();
for(int i=1;i<=n;i++){
ev.push_back({ui[i]-1,li[i],ri[i],-wi[i],i});
ev.push_back({di[i],li[i],ri[i],wi[i],i});
}
sort(ev.begin(),ev.end(),greater<tuple<ll,ll,ll,ll,int>>());
ti=n;
cnt++;
id=0;
T.build(0,szc-1,1);
for(int i=szr-1;i>=0;i--){
while(id<ev.size() && get<0>(ev[id])>=cr[i]){
auto [u,l,r,w,c]=ev[id++];
if(out[c]==cnt) continue;
cont[c].push_back({fdc(l),fdc(r),w});
T.update(0,szc-1,1,fdc(l),fdc(r),w);
}
while(T.query(0,szc-1,1,0,szc-1)>=x && ti){
td[ti]=cr[i];
out[ti]=cnt;
for(auto [l,r,w]:cont[ti]){
T.update(0,szc-1,1,l,r,-w);
}
ti--;
}
if(ti==0) break;
}
// for(int i=1;i<=n;i++){
// cout<<ta[i] <<" " <<tb[i] <a<" " <<tc[i] <<" " <<td[i] <<"\n";
// }
for(int i=1;i<=n;i++){
if(ta[i]==0 || tb[i]==0 || tc[i]==0 || td[i]==0) cout<<0 <<"\n";
else cout<<(tb[i]-ta[i]+1LL)*(td[i]-tc[i]+1LL) <<"\n";
}
}
