卡常

#include<bits/stdc++.h>
#define y1 y111
using namespace std;
typedef long long ll;
const int N=3e5+5,b=547;
int reb_tim;
vector<array<int,3>> a[N];
int n,m,cnt;
int c[N],to[N],tg[N],val[N];
ll ans[N];
vector<int> op[N];
void rep(int x){
	int now=0,delta=0;
	vector<int> rec;
	for(int i:op[x]){
		now-=i;
		if(now<0) now+=m;
		if(now>=m) now-=m;
		delta+=i;
		val[now]++;
		rec.push_back(now);
	}
	int l=b*x,r=min(b*(x+1)-1,n-1);
	for(int j=l;j<=r;j++){
		ans[to[j]]+=val[c[j]%m];
	}
	op[x].clear();
	for(int j:rec){
		val[j]=0;
	}
	for(int j=l;j<=r;j++){
		c[j]+=delta+tg[x];
		int u=c[j]%m;
		if(u<=m-u) to[j]=c[j]/m;
		else to[j]=c[j]/m+1;
	}
	tg[x]=0;
}
void rebuild(){
	for(int i=0;i<=(n-1)/b;i++){
		rep(i);
	}
}
void sol1(){
	int cnt[10][10]={};
	for(int i=1;i<=n;i++){
		int x1,x2,y1,y2;
		cin>>x1>>x2>>y1>>y2;
		x1--,x2--,y1--,y2--;
		x2--,y2--;
		for(int j=x1;j<=x2;j++){
			for(int k=y1;k<=y2;k++){
				cnt[j][k]++;
			}
		}
	}
	for(int j=0;j<n;j++){
		for(int k=0;k<n;k++){
			ans[cnt[j][k]]++;
		}
	}
	for(int i=m;i<=n;i+=m){
		cout<<ans[i]<<"\n";
	}
	exit(0);
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>m;
	if(n<=5){
		sol1();
	}
	reb_tim=max(1,(m-1)/2);
	for(int i=1;i<=n;i++){
		int x1,x2,y1,y2;
		cin>>x1>>x2>>y1>>y2;
		x1--,x2--,y1--,y2--;
		x2--,y2--;
		a[y1].push_back({x1,x2,1});
		a[y2+1].push_back({x1,x2,-1});
	}
	int cnt=0;
	for(int h=0;h<n;h++){
		for(auto [l,r,k]:a[h]){
			if((++cnt)%reb_tim==0){
				rebuild();
			}
			int bl=l/b,br=r/b;
			if(bl==br){
				rep(bl);
				for(int j=l;j<=r;j++){
					c[j]+=k;
				}
				continue;
			}
			rep(bl);
			for(int j=l;j<(bl+1)*b;j++){
				c[j]+=k;
			}
			for(int j=bl+1;j<br;j++){
				tg[j]+=k;
			}
			rep(br);
			for(int j=br*b;j<=r;j++){
				c[j]+=k;
			}
		}
		for(int i=0;i<=(n-1)/b;i++){
			op[i].push_back(tg[i]);
			tg[i]=0;
			if(op[i].size()>=5e4) rebuild();
		}
	}
	rebuild();
	for(int i=1;i<=n/m;i++){
		cout<<ans[i]<<"\n";
	}
}