简单题，切掉了。

求你了 CCF 正赛放一个正常点的紫题吧。放个这种题也比 D1T1 和 sale 强多了吧。

首先题意转化为我们要求所有泥地的最小行坐标，另外三个方向同理。

显然随着时间的流逝，最小行坐标越来越小。

我们考虑对于每一个最小行坐标求出它作为答案的区间，那么行坐标越来越大，它作为答案的区间也越来越偏小。

将行坐标离散化，从小往大扫，并维护一个变量 $nw$ 表示当前最后一个没有确定答案的时间，并维护一个集合 $s$。假设当前行坐标是 $j$，那么将满足 $u_i=j,i\le nw$ 的所有矩形拉出来，对于 $l_i,r_i$ 在 SGT 上做区间加法，并将 $i$ 加入集合 $s$。如果此时 SGT 上的最大值比 $x$ 大，那么找到此时 $s$ 中的最大值 $k$，此时 $k\sim nw$ 的答案必然是 $j$，然后将 $k-1$ 赋给 $nw$，将 $k$ 从 $s$ 中删去，并在 SGT 上减去贡献。然后一直执行以上过程，直到 SGT 上的最大值 $<x$。最后不要忘了对于 $i\le nw,d_i=j$ 的矩形，扣掉贡献，再往下一个行坐标扫。

时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int h,w,n,xx;
const int nn=4e5+5;
int u[nn],d[nn],l[nn],r[nn],res[nn],lsh[nn<<1],q[nn<<1],x[nn],y[nn],ans[4][nn],c[nn];
#define pb push_back
vector<int> inc[nn],del[nn];
struct node{
	int l,r,mx,tag;
};
node t[nn<<2];
set<int> s;
inline void build(int l,int r,int o){
	t[o].l=l,t[o].r=r,t[o].mx=t[o].tag=0;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(l,mid,o<<1),build(mid+1,r,o<<1|1);
}
void col(int o,int z){
	t[o].mx+=z;
	t[o].tag+=z;
}
inline void psd(int o){
	if(t[o].tag){
		col(o<<1,t[o].tag);
		col(o<<1|1,t[o].tag);
		t[o].tag=0;
	}
}
inline void update(int l,int r,int z,int o){
	if(t[o].l==l&&t[o].r==r) return col(o,z),void();
	psd(o);
	int mid=(t[o].l+t[o].r)>>1;
	if(l<=mid) update(l,min(mid,r),z,o<<1);
	if(r>mid) update(max(mid+1,l),r,z,o<<1|1);
	t[o].mx=max(t[o<<1].mx,t[o<<1|1].mx);
}
void sol(int opt){
	s.clear();
	int cnt=0,sl=0;
	for(int i=1;i<=n;i++) lsh[++cnt]=u[i],lsh[++cnt]=d[i],q[++sl]=l[i],q[++sl]=r[i],res[i]=0;
	sort(lsh+1,lsh+cnt+1);
	sort(q+1,q+sl+1);
	cnt=unique(lsh+1,lsh+cnt+1)-lsh-1;
	sl=unique(q+1,q+sl+1)-q-1;
	build(1,sl,1);
	for(int i=1;i<=n;i++){
		int tou=lower_bound(lsh+1,lsh+cnt+1,u[i])-lsh,tod=lower_bound(lsh+1,lsh+cnt+1,d[i])-lsh;
		inc[tou].pb(i),del[tod].pb(i);
		x[i]=lower_bound(q+1,q+sl+1,l[i])-q,y[i]=lower_bound(q+1,q+sl+1,r[i])-q;
	}
	int nw=n;
	for(int i=1;i<=cnt;i++){
		for(int id:inc[i]) if(id<=nw) update(x[id],y[id],c[id],1),s.insert(id);
		while(t[1].mx>=xx){
			auto it=prev(s.end());
			int id=*it;
			update(x[id],y[id],-c[id],1);
			for(int k=nw;k>=id;k--) res[k]=lsh[i];
			nw=id-1;
			s.erase(it);
		}
		for(int id:del[i]) if(id<=nw) update(x[id],y[id],-c[id],1),s.erase(id);
		inc[i].clear(),del[i].clear();
	}
	for(int i=1;i<=n;i++) ans[opt][i]=res[i];
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>h>>w>>n>>xx;
	for(int i=1;i<=n;i++) cin>>u[i]>>d[i]>>l[i]>>r[i]>>c[i];
	sol(0);
	for(int i=1;i<=n;i++) u[i]=h-u[i]+1,d[i]=h-d[i]+1,swap(u[i],d[i]);
	sol(1);
	for(int i=1;i<=n;i++) swap(u[i],d[i]),u[i]=h-u[i]+1,d[i]=h-d[i]+1,swap(u[i],l[i]),swap(d[i],r[i]);
	sol(2);
	for(int i=1;i<=n;i++) u[i]=w-u[i]+1,d[i]=w-d[i]+1,swap(u[i],d[i]);
	sol(3);
	for(int i=1;i<=n;i++){
		if(ans[0][i]==0) cout<<0<<"\n";
		else cout<<(h-ans[1][i]+1-ans[0][i]+1)*(w-ans[3][i]+1-ans[2][i]+1)<<"\n";
	}
	return 0;
}